反转链表

题目描述

反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：LeetCode

解法一

从前往后，每次反转后一个节点，维持两个指针prev和last，分别指向第一个和第二个节点，依次后移，直到链表结束同时因为last反转后，下一个节点的连接丢失，所以必须维持一个临时指针，保存last的下一个节点。结束时，置head节点为NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 == nullptr || head->next == nullptr) return head;
        ListNode * prev = head;
        ListNode * last = head->next;
        while(last) {
            ListNode * temp = last->next;
            last->next = prev;
            prev = last;
            last = temp;
        }
        head->next = nullptr;
        return prev;
    }
};

解法二

反转链表有点像栈，最简单的思路是节点指针存放在栈中，出栈时依次指向下一个在栈顶中的元素。

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
27
28
29
30
/**
 * 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 == nullptr) return head;
        stack<ListNode*> s;
        while(head) {
            s.push(head);
            head = head->next;
        }
        ListNode * cur; // 工作指针
        ListNode * newhead = s.top(); // 最开始的位置
        while(!s.empty()) {
            cur = s.top();
            s.pop();
            cur->next = nullptr;
            if(!s.empty()) {
                cur->next = s.top();
            }
        }
        return newhead;
    }
};

解法三

与栈的解法类似，可以用递归的方式模拟栈。递归首先要找出能递归的子问题，子问题的结构在递归时需要保持一致，每次递归都完成一点工作，最后递归过程结束时，就得到了问题的解。
反转链表中，首先依次递归到底部，找到结尾节点作为返回值，之后因为从倒数第二个节点开始，用p->next->next=p的方式完成后一个节点到当前节点的反转，递归结束退回到head。注意每次递归下一个节点返回，都把它的next置位nullptr，这是为了最后不用单独置head->next=nullptr，保持递归的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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 == nullptr || head->next == nullptr) return head;
        ListNode * newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};