题解 | #重排链表#
首先理清思路,重排链表的结果就是,合并前半部分和倒着的后半部分。
由此,确定两种思路:
O(n): 使用一个列表存储链表元素,前顺序,后逆序,直至相遇
O(1): 首先选取中间位置,翻转后半部分,合并两部分链表,这实际上是三个函数的代码,一定要对每一个步骤都心里有数
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ import java.util.*; public class Solution { public void reorderList(ListNode head) { // O(1): 首先选取中间位置,翻转后半部分,合并两部分链表 // O(n): 使用一个链表存储元素,逆序取 if (head == null || head.next == null) { return; } /* ListNode n = head; ArrayList<ListNode> list = new ArrayList<>(); while (n != null) { list.add(n); n = n.next; } // 交换 int l = 0, r = list.size() - 1; while (l < r) { list.get(l).next = list.get(r); list.get(r).next = list.get(l + 1); l++; r--; } list.get(l).next = null; */ // 获取中间位置 ListNode middle = getMiddle(head); ListNode n2 = reverse(middle.next); ListNode n1 = head, h1 = head; while (n1 != null) { if (n1.equals(middle)) { n1.next = null; } n1 = n1.next; } head = rebase(h1, n2); } private ListNode rebase(ListNode n1, ListNode n2) { if (n1 == null || n2 == null) { return null; } ListNode h1 = n1, h2 = n2, next1 = h1.next, next2 = h2.next; while (n1 != null && n2 != null) { next1 = n1.next; next2 = n2.next; n1.next = n2; if (next1 != null) { n2.next = next1; } n1 = next1; n2 = next2; } return h1; } private ListNode getMiddle(ListNode head) { if (head == null || head.next == null) { return head; } ListNode fast = head, slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } System.out.println(slow.val); return slow; } private ListNode reverse(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pre = null, node = head, next = head.next; while (node != null) { next = node.next; node.next = pre; pre = node; node = next; } System.out.println(head.val); return pre; } }