剑指offer-反转链表

佚名 7年前 (2019-02-20) 算法 1216人围观抢沙发百度已收录

反转链表

一、题目描述

输入一个链表，反转链表后，输出新链表的表头。
（看过答案和测试之后，题目隐藏条件是要求链表是不带头结点的）

二、题目思路

就是用三个指针，head、pre、next，head之前都是已经反转好了的链表，next及之后的结点属于还没有反转的链表。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

三、算法实现

3.1、Java实现

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre=null;
        ListNode next=null;
        
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}

以下画了一个示意图

3.2、C++实现

同样的思路：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre=NULL;
        ListNode *next=NULL;
        
        while(pHead!=NULL){
            next=pHead->next;
            pHead->next=pre;
            pre=pHead;
            pHead=next;
        }
        
        return pre;
    }
};