字节一面，面试官告诉我链表掌握的不熟练

小灰灰 2022-12-06 12:34 39阅读 0赞

大家好，我是吴师兄，今天分享一道很有技术含量的算法题，这道题目考察了链表的好几个知识点，近半年内，在字节跳动的面试环节出现了数十次。

### 题目描述 ###

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

题目来源：https://leetcode-cn.com/problems/reorder-list/

### 题目解析 ###

题目给的信息量不多，输入一个链表，然后让你按一定的规则变换链表节点的位置。变换信息如下：

L0→L1→…→Ln-1→Ln
        变换为
    L0→Ln→L1→Ln-1→L2→Ln-2→…

并且题目要求不能改变节点的值。

这道题目属于链表题目中较为复杂的一类，考察了常见的链表操作，很能锻炼编程的基本功。

拿到题目，我们首先需要思考的是，**我们该如何变换成第二种格式**？

对比发现，链表的前半部分好像和后半部分交叉在一起了，但是貌似后半部分和前半部分并不是平行着交叉在一起。

再看，前半部分的下标是在递增的，后半部分的下标是在递减的。

到这里，你应该可以知道后半部分是在反转之后，再与前半部分进行交叉的。

基本上这道题目的思路就是这样，一般来说，**链表的题目并不是难在思路上，而是难在具体的实现上面**，实在没有思路的话，**可以试着把链表当成数组来思考**。

解决这道题目有三个步骤，这三个步骤都可以单独拿出来作为链表的考察。

第一步是 **找链表的中点**，这里我们需要用到快慢指针这一技巧，需要注意的是，我们要根据题目的要求来调节快慢指针的起始位置，这个拿几个例子跑跑大概就能知道。

第二步是 **反转链表**，一般来说用普通循环实现的话，需要三个指针交替完成。

第三步是 **合并链表**，这一步相对前两步来说，思考难度会小一点，需要注意的一点是，出了循环，我们仍然要判断。

更具体的，就看代码实现吧。**链表相关的题目，主要还是考多练，它的操作其实并不多**。

### 参考动画 ###

### 参考图片 ###

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

### 参考代码 ###

public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
    
        // 步骤 1: 通过快慢指针找到链表中点
        // 通过调节快慢指针的起始位置，可以保证前半部分的长度大于等于后半部分
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
    
        // 步骤 2: 反转后半部分的链表
        // 在反转之前需要的一个操作是将前后半部分断开
        ListNode second = slow.next;
        slow.next = null;
        second = reverseList(second);
    
        // 步骤 3: 合并前半部分链表以及反转后的后半部分链表
        mergeList(head, second);
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null, tmp = null, pointer = head;
        while (pointer != null) {
            tmp = pointer.next;
            pointer.next = prev;
            prev = pointer;
            pointer = tmp;
        }
    
        return prev;
    }
    
    private void mergeList(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;
    
        while (first != null && second != null) {
            pointer.next = first;
            first = first.next;
            pointer.next.next = second;
            second = second.next;
            pointer = pointer.next.next;
        }
    
        // 因为我们之前找中点的时候保证了前半部分的长度不小于后半部分的长度
        // 因此交叉后，多出来的部分只可能是前半部分，判断前半部分即可
        if (first != null) {
            pointer.next = first;
        }
    }

推荐阅读：

[抱歉！你们曾经下过哪些成人影片，都被这个站记下了][Link 1]

[我去，还有这种网站][Link 2]

[迅雷，终于回来了！][Link 3]

![format_png 20][]

[format_png]: /images/20221123/5172e3c8c5964f589ff27271c502afaa.png
[format_png 1]: /images/20221123/18cfde1947fb43f0866e8673e2bd5764.png
[format_png 2]: /images/20221123/4ea1f7ad5e7b4921bad27741c8347b1d.png
[format_png 3]: /images/20221123/5de423bcb0e54fbf9539d8a16a92585e.png
[format_png 4]: /images/20221123/e692058bc2294ef8bf8589fb76b0cb40.png
[format_png 5]: /images/20221123/cc5d3b879fac4a2db5c79ad5aa538860.png
[format_png 6]: /images/20221123/e3f662a9c37140c78f701bdcaa4d434a.png
[format_png 7]: /images/20221123/9766cbb02d29400ab00af70bc982c6db.png
[format_png 8]: /images/20221123/59cea620fa3f42a280c33c75ce9279f2.png
[format_png 9]: /images/20221123/d9ec384a5b664272ae8ec411f32b9167.png
[format_png 10]: /images/20221123/d056c166e1b64bd6a9605a6a495292ad.png
[format_png 11]: /images/20221123/6e78345378fe4b23950655fb5bb35b9d.png
[format_png 12]: /images/20221123/3b2ff60057544f489e5d37a8daa73653.png
[format_png 13]: /images/20221123/cb42136812b740a091494f8bee7e62ce.png
[format_png 14]: /images/20221123/21d962542921408083fc4722badc273e.png
[format_png 15]: /images/20221123/8ebc122b6748423cae611200829ebd7b.png
[format_png 16]: /images/20221123/6eb4971b09ed40568bff5909aa96a918.png
[format_png 17]: /images/20221123/f3f88e8bef0642abbace706379d84dad.png
[format_png 18]: /images/20221123/3f81e624b8ef493f972db17dce63db90.png
[format_png 19]: /images/20221123/cb8ef4059bc648e3b7c3394571b00519.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU1ODg0OTkxNQ%3D%3D&chksm=fc210c77cb56856140f8c1934042442d83c5421149e0a6abe3b1f45521567d98428dd08994fe&idx=1&mid=2247485027&scene=21&sn=25763c139166d29990b49f891a283857#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d8926cd7a0030224e5372476a3edf5ecb1addef6d17a4d15cdc548d1ccaaca7aa93d0c518&idx=2&mid=2247493287&scene=21&sn=6388436c3ba81579836b9f3247bfbe20#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzU1ODg0OTkxNQ%3D%3D&chksm=fc210c24cb568532dfca8894845d75d9b7dc55dda6df1a120bb3572719e54a5b66857bec8870&idx=1&mid=2247484976&scene=21&sn=295ad24ced2e68de6d93a5bf144c76da#wechat_redirect
[format_png 20]: /images/20221123/5072b14ad53a4420844f8d19677446e5.png