[LeetCode]77. Reverse Linked List反转链表

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Subscribe to see which companies asked this question

解法1：一个最简单的办法就是借助栈的后进先出功能，先扫描一遍链表保存每个节点的值，然后再从头到尾遍历，将栈中元素值一一赋给链表节点。时空复杂度都是O(n)。

/**
 * 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) {
        stack<int> elem;
        ListNode* curr = head;
        while(curr != NULL) {
            elem.push(curr->val);
            curr = curr->next;
        }
        curr = head;
        while(curr != NULL) {
            curr->val = elem.top();
            curr = curr->next;
            elem.pop();
        }
        return head;
    }
};

解法2：可以做到in-place的反转。链表反转后，实际上只是中间节点的指针反转，并且反转后原来链表的头结点的下一个节点应该为NULL，而反转后链表的头结点为原来链表的尾节点。我们可以从头结点开始，每次处理两个节点之间的一个指针，将其反转过来。然后再处理接下来两个节点之间的指针……直至遇到尾节点，设置为新链表的头结点即可。

/**
 * 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) {
        ListNode* rHead = NULL; // 反转后的头节点
        ListNode* curr = head; // 当前处理节点
        ListNode* pTail = NULL; // 反转后尾节点
        while(curr != NULL) {
            ListNode* pNext = curr->next;
            if(pNext == NULL)
                rHead = curr;
            curr->next = pTail;
            pTail = curr;
            curr = pNext;
        }
        return rHead;
    }
};

上面的是一个循环来进行反转。递归的方式如下：

/**
 * 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 || head->next == NULL) return head;
        ListNode* rHead = reverseList(head->next); // 反转得到新链表的头节点
        head->next->next = head; // 当前节点的下一个节点的next指针反转过来
        head->next = NULL; // 设置新链表的尾节点
        return rHead;
    }
};