关于java:链表反转全家桶三动画详解两两交换链表中的节点

上回说到的是单链表反转的“二哥” —— 两两替换链表中的节点。明天来剖析一下它的大哥：“K个一组翻转链表”。

题目形容如下。

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

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

如果节点总数不是 k 的整数倍，那么请将最初残余的节点放弃原有程序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，该当返回: 2->1->4->3->5

当 k = 3 时，该当返回: 3->2->1->4->5

如果一上来就做K个一组翻转链表这个题，难度还是比拟大的，如果后面有了它两个弟弟的铺垫，那么这道题目就是瓜熟蒂落的了，后面两道题目的答案联合起来就是这道题目的答案了。这道题目和它两个兄弟一样，也能够应用迭代和递归两种办法解决。

办法一：三指针迭代

有了上回单链表反转的双指针迭代法的根底，再来解决它二哥，就绝对容易很多了。
“巧妇难为无米之炊”。题目中说的是K个一组翻转，那首先得有K个节点才行，和“两两替换链表中的节点”一样，上来先判断够K个节点才持续替换，而且循环持续的条件也是要满足剩下的节点够K个才行。
咱们能够应用两个变量left和right来示意以后要进行翻转的一段链表中的起始节点和完结节点。

如上图，指针L和R别离示意一段要进行翻转的链表中的起始节点和完结节点，如何找到一段链表中的第K个节点，咱们能够写一个办法来实现，如果剩下的链表的长度够K个，就返回第K个节点的指针，反之返回null：

<code class="java">private ListNode findKthNode(ListNode p, int k) {
  int curCount = 0;
  while (curCount < k - 1 && p != null) {
    p = p.next;
    curCount++;
  }
  return (curCount == k - 1) ? p : null;
}

指针L和R之间的节点怎么进行翻转，和链表反转全家桶（一）：动画详解单链表反转中的办法是一样的，惟一区别是“单链表反转”中完结的指针是尾指针，而这里完结的指针是指定的 —— 每段链表的第K个节点。有迭代和递归两种，为了放弃办法的一致性，这里还用迭代法。实现代码如下：

<code class="java"> private void reverseRange(ListNode left, ListNode right) {
    if (left == right) {
    <a style="color:transparent">来源gao*daima.com搞@代#码网</a>  return;
    }
    ListNode exit = right.next;
    ListNode cur = left, pre = null;
    while (cur != exit) {
      ListNode next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
}

同时，要思考上面的这种场景，第一段的K个节点曾经实现翻转，当初轮到第二段链表进行翻转，实现之后，pre须要指向R节点，所以还要记录每一轮替换的前驱节点，下图这个例子外面前驱节点就是节点1。

整体的代码实现如下：

<code class="java">class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode pre = null, left = head, right = findKthNode(head, k);
    if (right == null) {
      return head;
    }
    ListNode ans = right;
    while (left != null && right != null) {
      ListNode next = right.next;
      reverseRange(left, right);
      left.next = next;
      if (pre != null) {
        pre.next = right;
      }
      pre = left;
      left = next;
      right = findKthNode(next, k);
    }
    return ans;
  }

  private void reverseRange(ListNode left, ListNode right) {
    if (left == right) {
      return;
    }
    ListNode exit = right.next;
    ListNode cur = left, pre = null;
    while (cur != exit) {
      ListNode next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
  }

  private ListNode findKthNode(ListNode p, int k) {
    int curCount = 0;
    while (curCount < k - 1 && p != null) {
      p = p.next;
      curCount++;
    }
    return (curCount == k - 1) ? p : null;
  }
}

察看一下下面的代码，它和“两两替换链表中的节点”的构造是一样的。下图为代码比照，能够看到1，2，3处的代码模式是一样的，“两两替换链表的节点”是“K个一组翻转链表”在K=2时的特例。

复杂度剖析

• 工夫复杂度：O(n)。
• 空间复杂度：O(1)。

办法二：递归

递归法同样是它的两个小弟的联合。

一个链表段内的翻转的递归写法和“单链表的翻转”是一样的，惟一不同点是递归退出条件不同，链表段的翻转递归退出条件是左指针和右指针相遇，而单链表反转的退出条件是以后节点为空或以后节点曾经是尾节点。

同样，它的整体写法和“两两替换链表中的节点”是一样的，“两两替换链表中的节点”是“K个一组翻转链表”在K为2时的特例。

代码如下：

<code class="java">class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    ListNode left = head, right = findKthNode(head, k);
    if (right == null) {
      return left;
    }
    ListNode next = reverseKGroup(right.next, k);
    reverseRange(left, right);
    left.next = next;
    return right;
  }

  private void reverseRange(ListNode left, ListNode right) {
    if (left == right) {
      return;
    }
    reverseRange(left.next, right);
    left.next.next = left;
    left.next = null;
  }

  private ListNode findKthNode(ListNode p, int k) {
    int curCount = 0;
    while (curCount < k - 1 && p != null) {
      p = p.next;
      curCount++;
    }
    return (curCount == k - 1) ? p : null;
  }
}

复杂度剖析

• 工夫复杂度：O(n)。
• 空间复杂度：O(n)，应用了递归，递归的栈深度为n。

喜欢 (0)赏

[搞代码]

分享 (0)