[LeetCode 206] Reverse a singly 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?

Diffculty
Easy

Similar Problems
[LeetCode ] Word Pattern Easy

Analysis

算法1: pre 指针 算法2: Dummy Head

cur
1 ————> 2 ————> 3 ————> 4 ————> 5
^
|

dummyhead ------------> / cur \ 1 <———— 2 <———— 3 ————> 4 ————> 5 ^ | dummyhead 过程: 把当前节点指向它的下一个的下一个节点， 然后把它自己的下一个节点指向当前节点 把它下一个节点的下一个节点再指向它的下一个节点 把dummyhead指向它的下一个节点

Solutions

一、 pre 指针

class Solution {
public:
    ListNode* reverseList(ListNode *head){
        ListNode *pre = nullptr;
        while(head != nullptr){ // reverse from node 0
            ListNode *temp = head->next;
            head->next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
};

二、dummy node

class Solution {
public:
    ListNode* reverseList(ListNode* head){
       if(head == nullptr || head->next == nullptr) return head;
       ListNode dummyhead(0);
       dummyhead.next = head;
       ListNode* cur = head;
       while(cur->next != nullptr){
           ListNode* tmp = cur->next;
           cur->next = tmp->next;
           tmp->next = dummyhead.next;
           dummyhead.next = tmp;
       }
       return dummyhead.next;
    }
};