【每日算法Day 88】翻转链表系列问题

反转链表有关的问题基本上都有递归解法和迭代解法，并且复杂问题的解法往往可以重复利用基本问题的解法，例如反转第m到第n个节点可以利用反转前K个节点的方法、每K个一组反转可以稍加改造后利用反转全部链表的解法。

LeetCode 206. 反转链表 (opens new window)

题目描述

反转一个单链表。

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

递归思路：递归终止条件是当前节点的下一个节点为空（该节点就是反转后的头节点）或当前节点为空（仅当一开始的输入为空时才会达到），返回该头节点。先递归地处理当前节点之后的部分，得到反转后部分的头节点便于在最后传递返回该头节点。在返回新头节点之前，需要把当前节点的next节点的next指针设为当前节点，再把当前节点的next指针设为null，这样就实现了局部的翻转。

public ListNode reverseList(ListNode head){
    if(head == null || head.next == null) return head;
    ListNode reversedHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reversedHead;
}

迭代思路：使用两个指针来操作链表，pre初始为空表示翻转过程中前面的节点，cur初始为head表示翻转过程中当前的节点。在迭代过程中每次使用临时变量temp保存cur后面的节点的引用便于下次迭代，之后就可以将cur的next指针指向pre，并分别将pre指向cur、将cur指向temp以便于下次迭代。迭代的终止条件是cur为空，这时pre就应该是该返回的节点。

public ListNode reverstList(ListNode head){
    //if(head == null || head.next == null) return head;
    ListNode pre = null, cur = head;
    while(cur != null){
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

反转链表的前N个节点

解题思路

递归思路：递归终止的条件是反转以当前节点开始计算的链表的前1个节点，这时当前head就是反转后链表的新头节点，当前节点的下一个节点就是原链表反转部分的下一个节点，用一个全局变量保存。递归继续进行的情况下，对当前节点的next节点递归调用方法，得到最终的新头节点后，反转当前节点和后继节点的关系，并把当前节点的后继设为已经保存在全局变量中的后继节点。

private ListNode successor = null;
public ListNode reverseToNth(ListNode head, int n){
    if(n == 1 || head.next == null){
        successor = head.next;
        return head;
    }

    ListNode newHead = reverseToNth(head.next, n - 1);
    head.next.next = head;
    head.next = successor;
    return newHead;
}

迭代思路：和上一题类似，不过在迭代时增加一个计数器，当反转到第N个节点之后就把原head的next指针指向当前节点的next，完成N-1和N的反转并返回第N个节点。

public ListNode reverseToNth(ListNode head, int n){
    if(head == null) return head;
    ListNode pre = null, cur = head, temp = null;
    int count = 1;
    while(cur != null && count <= n){
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
        count++;
    }
    head.next = temp;
    return pre;
}

LeetCode 92. 反转链表II (opens new window)

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。1 ≤ m ≤ n ≤ 链表长度。

示例

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路

递归思路：在前面的基础上，这里就相当于找到第m个位置，以该节点为第一个节点一直反转到原来第n个位置。那么同样地可以迭代地实现找到第m个位置的过程。

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) return reverseToNth(head, n); //这里任选上面的递归或迭代解法均可
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

迭代思路：使用两个个变量保存第m-1、m个节点，在遍历到m时为这两个变量赋值；在m和n之间进行反转；在遍历到第n个节点时，将第m-1个节点的next设为第n个节点，把第m个节点的next设为第n+1个节点，跳出循环。为了避免空指针和m=1的情况导致没有第m-1个节点，使用一个dummy节点指向头节点再进行迭代，最后返回dummy.next。

public ListNode reverseBetween0(ListNode head, int m, int n) {
    if(m == n) return head;
    ListNode part1Tail = null, part2Head = null;
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    int count = 1;
    ListNode prev = dummy, curr = head;
    while (curr != null) {
        if (count == m) {
            //标记
            part1Tail = prev;
            part2Head = curr;
        }
        ListNode temp = curr.next;
        if (count > m && count < n) {
            //翻转
            curr.next = prev;
        }
        if (count == n) {
            part2Head.next = curr.next;
            part1Tail.next = curr;
            curr.next = prev;
            break;
        }
        //跳跃
        prev = curr;
        curr = temp;
        count++;
    }
    return dummy.next;
}

LeetCode 25. K 个一组翻转链表 (opens new window)

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

解题思路

我们观察题目的描述，发现具有子问题的性质，那么可以用递归的方法来做。我们可以从头节点开始数K节点，如果剩余不足K个节点那么不用反转这部分了直接返回头节点；否则我们能找到这部分的第1个节点、第K个节点和第K+1个节点，我们对1~K个节点进行反转得到反转后的头节点，并将反转后的尾节点的next设为对K+1个节点递归调用本方法得到的头节点，最终返回头节点。

至于对1~K个节点进行反转这部分，我们可以回顾第一题完全反转一个链表，无论是递归还是迭代的终止条件都是cur.next == null，那么我们只需要把终止条件改为cur.next == 第K+1个节点即可。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode a = head, b = head;
    for (int i = 0; i < k; i++) {
        if (b == null) return a;
        b = b.next;
    }
    ListNode newHead = reverseInRange(a, b);
    a.next = reverseKGroup(b, k);
    return newHead;
}

private ListNode reverseInRange(ListNode head, ListNode tailNext){
    ListNode pre = null, cur = head;
    while (cur != tailNext) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}