链表反转总结

1. 反转整个链表

递归反转链表

比如现在有这样一个链表：
(K_1 ightarrow K_2 ightarrow ... ightarrow K_{i} ightarrow K_{i+1} ightarrow ... ightarrow K_{n})
若(K_{i})之后的链表都已经完成了反转，如下：
(K_1 ightarrow K_2 ightarrow ... ightarrow K_{i}leftarrow K_{i+1}leftarrow ... leftarrow K_{n})

下一步该如何操作呢？
Ki->next->next = ki

因此可以据此写出递归代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
};

时间复杂度：(O(n))
空间复杂度：(O(n))

迭代反转链表

定义一个prev指针作为新链表头指针，使用头插法将待反转链表中的节点按顺序插入到prev链表中，返回。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while (curr != nullptr) {
            ListNode* tmp = curr->next; 
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }

        return prev;
    }
};

时间复杂度：(O(n))
空间复杂度：(O(1))

2. 链表中部分节点的反转

对于链表中部分节点的反转，分为三步：

• 定位到待反转的节点
• 断链+反转
• 连接断链

代码实现：

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

        // 定位，使curr指向第m个节点
        ListNode *prev = nullptr, *curr = head;
        while (m > 1) {     
            prev = curr;
            curr = curr->next;
            --m;
            --n;
        }

        // 断链反转，得到反转后的链表third
        ListNode *tail = curr, *third = nullptr, *tmp;
        while (n > 0) {     
            tmp = curr->next;
            curr->next = third;
            third = curr;
            curr = tmp;
            --n;
        }

        // 重新连接上断链
        tail->next = tmp;
        if (prev != nullptr) {  
            prev->next = third;
        } else {          
            head = third;    // 若m=1，将断链的头指针赋给head
        } 
            
        return head;
    }
};

时间复杂度：(O(n))
空间复杂度：(O(1))

总结

对于链表反转的题目，最简单的办法就是新建一个数组来保存链表，然后逆序地重新构建新链表，但是这种做法的时间和空间开销都比较大；更好的办法是在原链表上直接反转，即前述的两种方法：迭代头插法与递归反转，迭代头插法效率高，而递归反转的代码实现非常简洁。
在做链表题的时候在纸上画一下图能够使操作过程变得更清晰。