链表反转的技巧及相关题解

单链表作为一种比较常见的数据结构，经常会出现在面试题中。单链表只有一个后继指针，要实现O(1)空间复杂度的反转，就需要掌握单链表反转的一些技巧。

注：我们这里讨论的都是如何不借助额外空间（即O(1)空间复杂度），实现链表反转。
首先让我们先看看最简单的链表反转：

1. 链表反转（简单）

206. 反转链表
剑指 Offer 24. 反转链表
剑指 Offer II 024. 反转链表
题目描述：把一个单链表反转，并返回反转后的链表头。
解题过程：

• 这道题可以很容易地用双指针解决：定义两个指针一个指向前驱节点prev，一个指向当前节点cur。
• 每一次迭代，反转当前节点后继指针的指向方向，然后前移前驱指针prev和当前指针cur
• 当前指针cur为空时说明到达链表尾部，遍历结束，返回前驱指针prev即为新链表的头指针。

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while(head){
        auto temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

代码如上所示，非常简单。这个O(1)空间复杂度的反转链表的关键就是反转的过程:

auto temp = head->next;
head->next = prev;
prev = head;
head = temp;

技巧1：写正确这个反转的关键就是这几行代码一定是链式赋值的，即A=B,B=C,C=A 这样的过程。
如果你写的不是链式赋值，代码逻辑肯定有问题。很多O(1)空间操作都是这种链式赋值，比如交换数值、链表删除节点等。

2.判断汇文链表（简单）

234. 回文链表
剑指 Offer II 027. 回文链表
解题过程：使用快慢双指针，找到链表中间位置，然后从中间位置反转链表后判断新链表和旧链表是否一致。

bool isPalindrome(ListNode* head) {
    auto slow = head;
    auto fast = head;
    while(fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    auto node2 = reverseList(slow->next);
    auto node1 = head;
    while(node1 && node2){
        if(node1->val != node2->val) 
            return false;
        node1 = node1->next;
        node2 = node2->next;
    }
    return true;
}
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while(head){
        auto temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

3.区间反转链表（中等）

92. 反转链表 II
题目描述：给你单链表的头指针 head 和位置区间left和right。请你反转从位置left到位置right的链表节点，返回反转后的链表。
这次的问题不是从头到尾反转链表，反转链表之前要找到反转的起始位置和结束位置，反转结束条件需要稍作调整：由当前节点为空改当前节点到达结束节点后的节点。

ListNode* reverseList(ListNode* head, ListNode* end) {
    ListNode* prev = nullptr;
    while(head != end){
        auto temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

反转函数稍做了一点调整，下面是遍历找到反转起终位置并反转链表的处理：

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if(left == right)
        return head;
    auto dummy = new ListNode(0, head);    
    int diff = right-left;
    auto start = dummy;
    auto end = dummy;
    auto prev = dummy;
    for(int i = 0; i < diff; i++){
        end = end->next;
    }
    for(int i = 0; i < left; i++){
        prev = start;
        start = start->next;
        end = end->next;
    }
    end = end->next;
    prev->next = reverseList(start, end);
    start->next = end;
    return dummy->next;
}

从上面的代码可以看到我们创建并使用了一个空节点dummy，以简化链表头部的处理。在这道题中反转区间有可能从头节点开始，因此头结点可能会被修改。有了这个dummy节点，你就不用去记录新的头节点是哪个了，反转处理完了之后dummy节点的后继节点就是新的头节点。
技巧2：凡是链表头指针可能会被修改的场景，一般都可以使用一个空节点来简化代码处理
此外这道题中还使用了双指针，因单链表单向遍历的特点，使用快慢双指针可以通过一次遍历同时找到区间的开始和结束位置。
技巧3：使用双指针，一次遍历找到链表中两个不同的节点位置

4.两两交换链表中的节点（中等）

24. 两两交换链表中的节点
题目描述：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
解题过程：与上题一样，头节点可能被修改，所以使用了dummy节点。因为有区间开始结束位置，所以也使用了双指针。
然后迭代查找反转区间的开始和结束位置，再做区间内的链表反转。

ListNode* swapPairs(ListNode* head) {
    auto dummy = new ListNode(0, head);
    auto begin = head;
    auto end = head;
    ListNode* prev = dummy;
    while(end){
        if(!end->next){
            prev->next = begin;
            break;
        }
        end = end->next->next;
        prev->next = reverseList(begin, end);
        prev = begin;
        begin = end;
    }
    return dummy->next;
}
ListNode* reverseList(ListNode* head, ListNode* end){
    if(!head) return nullptr;
    ListNode* prev = nullptr;
    while(head->next != end){
        auto temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    head->next = prev;
    return head;
}  

5.K个一组翻转链表（困难）

25. K 个一组翻转链表
题目描述：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
解题过程：与上题一样，头节点可能被修改，所以使用了dummy节点。因为有区间开始结束位置，所以也使用了双指针。
代码实现和上题也基本一样，只是查找区间开始结束位置略有不同。

ListNode* reverseKGroup(ListNode* head, int k) {
    if(k == 1 || !head || !head->next) return head;
    auto dummy = new ListNode(0, head);
    auto begin = head;
    auto end = head;
    ListNode* prev = dummy;
    while(end){
        int i = 0;
        while(i < k && end){
            end = end->next;
            i++;
        }
        if(i < k){
            prev->next = begin;
            break;
        }
        prev->next = reverseList(begin, end);
        prev = begin;
        begin = end;
    }
    return dummy->next;
}
ListNode* reverseList(ListNode* head, ListNode* end){
    if(!head) return nullptr;
    ListNode* prev = nullptr;
    while(head->next != end){
        auto temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    head->next = prev;
    return head;
}

总结

通过学习一中基本问题的高效解法，使之稍加调整就能应用到其他相似问题，从而触类旁通，加深对问题解决方法的理解。