刷题日记-重排链表_重排链表 分数 14 作者 陈越 单位 浙江大学 给定一个单链表 l1→l2→ →ln

重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * $10^4$]
1 <= node.val <= 1000
思路
乍看这题十分复杂，但仔细思考后发现原题可以拆解成找到链表中点、反转链表和拼接链表三个过程。首先，找到链表中点，将中点右边的部分进行翻转，之后将两个链表中的节点依次合并即可
代码

class Solution {
     public ListNode reverse(ListNode head) {
         ListNode pre = null;
         ListNode cur = head;
         ListNode next = null;
         while(cur!=null){
             next = cur.next;
             cur.next = pre;
             pre = cur;
             cur = next;
         }
         return pre;
    }
    public void reorderList(ListNode head) {
        if(head==null) return ;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode head2 = reverse(slow.next);
         slow.next = null;
        ListNode cur = head;
        ListNode cur2 = head2;
        ListNode next = null;
        ListNode next2 = null;
        while(cur2!=null){
            next2 = cur2.next;
            next = cur.next;
            cur.next = cur2;
            cur2.next = next;
            cur=next;  
            cur2 = next2;
        }
        return;
    }
}
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