剑指Offer系列24—反转链表

题意

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

题解

方法一：迭代+双指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return NULL;

        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* p; //用来暂存cur->next;

        while(cur != NULL){
            p = cur->next;
            cur->next = pre;
            pre = cur;
            cur = p;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return NULL;
        ListNode* p = head->next;
        ListNode* pre = head;
        while(p != NULL){
            head->next = p->next;
            p->next = pre;
            pre = p;
            p = head->next;
        }
        return pre; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);           // 调用递归并返回
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre) {
        if (cur == nullptr) return pre;        // 终止条件
        ListNode* res = recur(cur->next, cur); // 递归后继节点
        cur->next = pre;                       // 修改节点引用指向
        return res;                            // 返回反转链表的头节点
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head->next == NULL) return head;
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return last;
    }
};
1
2
3
4
5
6
7
8
9
10