143. 重排链表

题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

img

输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：

img

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

思路

  1. 找到中间节点
  2. 翻转右边的链表
  3. 原左边的链表和右边的链表合并

这个题的主要难点：

  1. 拿到中间节点的时候，我们要考虑引用的链表在什么情况下会改变原来的值，当我们直接置空的时候不会改变原来饿值，但是我们next=null的时候会改变原来的值，所以我们可以直接返回中间节点的上一个节点

  2. 然后通过 mid.next = null;改变原来节点的值，划分出leftNode 和 rightNode

  3. 然后翻转链表，两个链表合并

    1. 链表合并的之后，我们之前是创建一个新的虚拟头节点，然后不断在虚拟头节点中国加入

    2. 现在因为没有返回值，所以我们需要在原来的head节点中操作

      1
      2
      3
      4
      5
      6
      7
      8
      headLeftTemp = headLeft.next;
      headRightTemp = headright.next;
      // 这个时候headLeft.next = headright;当我们改变headright的时候，这个head的节点的值也随之改变
      headLeft.next = headright;
      headLeft = headLeftTemp;

      headright.next = headLeft;
      headright = headRightTemp;

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode mid = middleNode(head);
    ListNode headLeft = head;
    ListNode headRight = mid.next;
    mid.next = null;
    headRight = reserveNode(headRight);
    mergeNode(headLeft, headRight);
}


private ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}


private ListNode reserveNode(ListNode head) {
    ListNode node = head;
    ListNode pre = null;
    while (node != null) {
        ListNode temp = node.next;
        node.next = pre;
        pre = node;
        node = temp;
    }
    return pre;
}

private void mergeNode(ListNode headLeft, ListNode headright) {
    ListNode headLeftTemp;
    ListNode headRightTemp;
    while (headLeft != null && headright != null) {
        headLeftTemp = headLeft.next;
        headRightTemp = headright.next;

        headLeft.next = headright;
        headLeft = headLeftTemp;

        headright.next = headLeft;
        headright = headRightTemp;

    }
}