143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

  • 个人认为这道题出的还是比较好的
  • 思路一：经典的思路 快慢指针找链表的中间节点，以及 头插法,递归，甚至可以使用 栈 来反转链表
  • 思路二：使用额外的存储空间，链表转化为数组 实现随机访问 ，或者转换为 双端队列实现头尾两端的访问
  • 思路三：比较难想的 递归 流程，可以复习和巩固对 递归 的使用
  • 三种思路，有很多的经典思路， 所以认为这道题还是挺有意思.
  • 接下来，分别是三种思路分析 和 代码实现

思路一 :

快慢指针 找 中间节点，配合 链表反转

  • 快慢指针 找到链表的中间节点

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    /**
     *
     * 快慢指针 查找 链表中间节点
     *
     * */
    public ListNode middle(ListNode head){
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;
        return slow;
    }

  • 反转链表的中间节点

    • 递归

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

      /**
 *
 * 反转链表
 * 递归
 *
 * */
public ListNode reverseRecursive(ListNode head){
    if (head == null || head.next == null) return head;
    
    ListNode node = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return node;
}

    • 迭代头插法

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

      /**
 *
 * 反转链表
 * 迭代
 *
 * */
public ListNode reverse(ListNode head){
    if (head == null || head.next == null) return head;
    ListNode newHead = null;
    ListNode node = head;
    while (node != null){
        ListNode tmp = node.next;
        node.next = newHead;
        newHead = node;
        node = tmp;
    }
    return newHead;
}

  • 拼接头节点 和 反转后的中间节点

代码如下 :

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/**
 *
 * 解法一 : 快慢指针找中间，反转后半段，再拼接
 *
 * 先快慢指针找到链表中间节点
 * 再反转后半部分链表
 *
 * 再拼接前半部分 和 反转后的后半部分
 *
 * */
public void reorderList1(ListNode head) {
    if (head == null || head.next == null) return;

    // 找到中间节点
    ListNode middle = middle(head);

    // 反转中间节点
    ListNode lastnode = reverseRecursive(middle);

    // 拼接 head 和 反转后的中间节点
    ListNode prevnode = head;
    while (prevnode != null && lastnode != null) {

        ListNode prev = prevnode.next;
        ListNode last = lastnode.next;

        prevnode.next = lastnode;
        lastnode.next = prev;

        prevnode = prev;
        lastnode = last;
    }

    if (prevnode != null) prevnode.next = lastnode;
}

/**
 *
 * 快慢指针 查找 链表中间节点
 *
 * */
public ListNode middle(ListNode head){
    if (head == null || head.next == null) return head;

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

    if (fast != null) slow = slow.next;

    return slow;
}

/**
 *
 * 反转链表
 * 递归
 *
 * */
public ListNode reverseRecursive(ListNode head){
    if (head == null || head.next == null) return head;

    ListNode node = reverseRecursive(head.next);
    head.next.next = head;
    head.next = null;

    return node;
}

复杂度分析 :

时间复杂度 : O(N)

空间复杂度 : O(1) 没有使用额外的存储空间

思路二 :

  • 链表不能实现随机访问， 在访问某节点时，只能通过head，找.next 。直到找到该节点
  • 所以我们遍历链表, 将链表中的节点都放入 数组 来实现节点的随机访问
  • 放入数组后，用头尾双指针拼接节点

代码如下:

 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

/**
 *
 * 解法二： 存储
 * 由于链表 不能随机访问
 * 所以，我们遍历链表， 把链表中的节点都放入 数组 实现随机访问
 *
 * 放入数组后，用头尾双指针拼接节点
 *
 * */
public void reorderList2(ListNode head) {
    if (head == null || head.next == null) return;

    ArrayList<ListNode> listNodes = new ArrayList<>();
    while (head != null){
        listNodes.add(head);
        head = head.next;
    }

    int i = 0, j = listNodes.size() - 1;
    while (i < j){
        listNodes.get(i).next = listNodes.get(j);
        i ++;

        // 奇数个节点，会提前相遇
        if (i == j) break;

        listNodes.get(j).next = listNodes.get(i);
        j --;
    }

    listNodes.get(i).next = null;
}

思路二: 变形

  • 使用双端队列
  • 首先依然遍历链表， 将链表中的节点，放入双端队列
  • 使用双端队列，实现链表节点，头尾节点的随机访问

代码如下 :

 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

/**
 *
 * 双端队列
 * 其实跟 数组差不多
 * 操作更方便一些
 *
 * */
public void reorderList3(ListNode head) {
    Deque<ListNode> queue = new LinkedList<>();
    ListNode cur = head;
    while (cur != null) {
        queue.addLast(cur);
        cur = cur.next;
    }
    while (!queue.isEmpty()) {
        if (cur == null) {
            cur = queue.pollFirst();
        } else {
            cur.next = queue.pollFirst();
            cur = cur.next;
        }
        cur.next = queue.pollLast();
        cur = cur.next;
    }
    if (cur != null) {
        cur.next = null;
    }
}

思路二复杂度分析:

时间复杂度 : O(N)

空间复杂度 : O(N) 使用了额外的 数组 或者 双端队列的存储空间

屏幕快照 2020-06-30 上午11.41.26

思路三: 递归

  • 个人认为，递归是三种解法中，最难想到的

  • 此解法来自 题解区 大神的题解, 点击查看 我这里只是将它贴出来，方便复习。

  • 解法一中也说到了，我们的问题就是取尾元素的时候，需要遍历一遍链表。

  • 如果我们的递归函数能够返回当前头元素对应的尾元素，并且将头元素和尾元素之间的链表按要求完成，那就变得简单了。

截屏2020-06-30下午9.30.28

 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

/**
 *
 * 解法三: 递归
 *
 * */
public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    int len = 0;
    ListNode node = head;
    while (node != null){
        len ++;
        node = node.next;
    }

    reorderListHelper(head, len);
}

/**
 *
 * 递归函数的作用是 找到 head 的尾元素
 *
 * */
public ListNode reorderListHelper(ListNode head, int len){
    if (len == 1){
        ListNode outTail = head.next;
        head.next = null;
        return outTail;
    }

    if (len == 2){
        ListNode outTail = head.next.next;
        head.next.next = null;
        return outTail;
    }

    //得到对应的尾节点，并且将头结点和尾节点之间的链表通过递归处理
    ListNode tail = reorderListHelper(head.next, len - 2);
    ListNode subHead = head.next;//中间链表的头结点
    head.next = tail;
    ListNode outTail = tail.next;  //上一层 head 对应的 tail
    tail.next = subHead;
    return outTail;
}