LeetCode-143. 重排链表

问题地址

LeetCode每日一题/2020-10-20

LeetCode143. 重排链表

问题描述

规则

给定一个单链表 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.

解析

解题思路

• 最直观的想法是使用线性表存储链表元素，然后遍历线性表，通过下标访问线性表中的元素重建链表。
• 使用线性表需要额外空间存储链表元素，再看看两外一个思路：
  • 找到链表中点；
  • 链表拆为前半段和后半段；
  • 反转后半段链表，合并两个链表；

数据操作分析

• 见思路分析

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

package fun.usb.algorithms.list;
import org.junit.Test;
public class LeetCode0143_ReorderList {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        //找中点
        ListNode mid = getMideNode(head);
        //定义前半段、后半段链表
        ListNode preList = head;
        ListNode postList = mid.next;
        //断开链表
        mid.next = null;
        //反转后半段链表
        postList = reverseList(postList);
        //合并链表
        mergeList(preList, postList);
    }

    private void mergeList(ListNode l1, ListNode l2) {
        ListNode l1Tmp = null;
        ListNode l2Tmp = null;
        while (l1 != null && l2 != null) {
            l1Tmp = l1.next;
            l2Tmp = l2.next;

            l1.next = l2;
            l1 = l1Tmp;

            l2.next = l1;
            l2 = l2Tmp;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode preNode = null;
        ListNode currNode = head;
        while (currNode != null) {
            ListNode tmp = currNode.next;
            currNode.next = preNode;
            preNode = currNode;
            currNode = tmp;
        }
        return preNode;
    }

    private ListNode getMideNode(ListNode head) {
        ListNode slowNode = head;
        ListNode fastNode = head;
        while (fastNode.next != null && fastNode.next.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return slowNode;
    }
}

官方解法

方法一 线性表

思路与算法：

因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。

因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。

复杂度分析：

1. 时间复杂度:O(N)，其中 N 是链表中的节点数。

2. 空间复杂度：O(N)，其中 N 是链表中的节点数。主要为线性表的开销。

编码实现

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}

方法二：寻找链表中点 + 链表逆序 + 合并链表

思路及算法：

• 注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
• 这样我们的任务即可划分为三步：
  • 找到原链表的中点（参考「876. 链表的中间结点」）。
    • 我们可以使用快慢指针来 O(N) 地找到链表的中间节点。
  • 将原链表的右半端反转（参考「206. 反转链表」）。
    • 我们可以使用迭代法实现链表的反转。
  • 将原链表的两端合并。
    • 因为两链表长度相差不超过 1，因此直接合并即可。

复杂度分析：

1. 时间复杂度:O(N)，其中 N 是链表中的节点数。
2. 空间复杂度：O(1)。

编码实现

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    public 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;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }
}

精彩评论

跳转地址1：详细通俗的思路分析，多解法

解法一 线性表

解法二 递归

参考 这里。

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

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

如上图，我们只需要将 head 指向 tail，tail 指向处理完的链表头即可。

然后我们把之前的 tail.next 返回就是外层 head 对应的 tail 了。

递归出口的话，如果只有一个节点，那么我们只需要将 head.next 返回。

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

如果是两个节点，我们需要将 head.next.next 返回。

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

##### 编码实现
然后总体的代码就是下边的样子
```java
public void reorderList(ListNode head) {

    if (head == null || head.next == null || head.next.next == null) {
        return;
    }
    int len = 0;
    ListNode h = head;
    //求出节点数
    while (h != null) {
        len++;
        h = h.next;
    }

    reorderListHelper(head, len);
}

private 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;
}

解法三

参考 这里，主要是利用到一头一尾取元素的特性。

主要是三步，举个例子。

1 -> 2 -> 3 -> 4 -> 5 -> 6
第一步，将链表平均分成两半
1 -> 2 -> 3
4 -> 5 -> 6

第二步，将第二个链表逆序
1 -> 2 -> 3
6 -> 5 -> 4

第三步，依次连接两个链表
1 -> 6 -> 2 -> 5 -> 3 -> 4

第一步找中点的话，可以应用 19 题 的方法，快慢指针。快指针一次走两步，慢指针一次走一步，当快指针走到终点的话，慢指针会刚好到中点。如果节点个数是偶数的话，slow 走到的是左端点，利用这一点，我们可以把奇数和偶数的情况合并，不需要分开考虑。

第二步链表逆序的话，在 第 2 题 讨论过了，有迭代和递归的两种方式，迭代的话主要利用两个指针，依次逆转。

第三步的话就很简单了，两个指针分别向后移动就可以。

编码实现

public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) {
        return;
    }
    //找中点，链表分成两个
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode newHead = slow.next;
    slow.next = null;

    //第二个链表倒置
    newHead = reverseList(newHead);

    //链表节点依次连接
    while (newHead != null) {
        ListNode temp = newHead.next;
        newHead.next = head.next;
        head.next = newHead;
        head = newHead.next;
        newHead = temp;
    }

}

private ListNode reverseList(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode tail = head;
    head = head.next;

    tail.next = null;

    while (head != null) {
        ListNode temp = head.next;
        head.next = tail;
        tail = head;
        head = temp;
    }

    return tail;
}

总结

解法一利用空间去存储就很简单了，解法二递归的思想也很经典，自己也想了很久，看到作者的思路才恍然大悟，判断当前 length 定义递归出口很巧妙。解法三主要就是对题目的理解，关键就是利用一头一尾取元素的特性。