leetcode *143. 重排链表（2020.10.20）

【题目】*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.

【解题思路1】双端队列

class Solution { public void reorderList(ListNode head) { if (head == null) return; Deque<ListNode> deque = new LinkedList<>(); ListNode cur = head.next; // head之后的节点入队 while (cur != null) { deque.add(cur); cur = cur.next; } // 双端队列头尾交替出队 cur = head; while (!deque.isEmpty()) { cur.next = deque.pollLast(); cur = cur.next; if (!deque.isEmpty()) { cur.next = deque.pollFirst(); cur = cur.next; } } cur.next = null;

【解题思路2】寻找链表中点 + 链表逆序 + 合并链表

找到原链表的中点（参考「876. 链表的中间结点」）。

将原链表的右半端反转（参考「206. 反转链表」）。

将原链表的两端合并（参考「21. 合并两个有序链表」）

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