leetcode_206 反转链表

1. 题意

原地反转链表，非常经典的一道题。

2. 解决

2.1 非递归

非递归的比较好理解；链表需要维护前驱和后继两个信息，当我们要更改后继时，先要把原来的后继先存起来。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        // A->B->C

        // next = getNext;
        // cur->next = pre
        // pre = cur;
        // cur =  next;
        // 
        //          pre
        //          |
        //          V
        //  null <- A    B->C 
        
        // null <- A     
    
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while ( cur ) {
            ListNode *nxt = cur->next;
            cur->next = pre;
            pre = cur;

            cur = nxt;
        }
        return pre;
    }

};

2.2 递归

递归的比较难理解一些 。

由于返回的是翻转后的头节点，因此需要不断的递归到没有后继节点的最后一个节点, 它就是反转后链表的头节点了。

而返回的链表的最后 一个节点是head->next ， 将它的指向改成当前节点。同时我们还需要将当前节点的next域置空，否则无法将原先的头指空。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        // A->B->C

        if ( head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode *newHead = reverseList( head->next );

        ListNode *newListTail = head->next;

        newListTail->next = head;
        head->next = nullptr;

        return newHead;
    }

};

3. 参考

[lc206]