LeetCode每日一题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.

/** * 节点类 */ public static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } ListNode(int val, ListNode next){ this.val = val; this.next = next; } }

solution1：

/** * 利用list的有序性 * 将链表存入list，顺序设置头尾 * @param head */ public void reorderList1(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return; } // 遍历链表将数据放入list List<ListNode> list = new ArrayList<>(); ListNode cur = head; while (cur != null) { list.add(cur); cur = cur.next; } // 定义i, j指针, i指向头、j指向尾 int i = 0, j = list.size() - 1; while (i < j) { // 将头节点.next指向尾结点 list.get(i).next = list.get(j); i++; // 将尾节点.next指向头结点 list.get(j).next = list.get(i); j--; } // 将最后的节点.next指向null list.get(i).next = null; }

执行结果： 执行用时：4 ms, 在所有 Java 提交中击败了28.22%的用户 内存消耗：40.6 MB, 在所有 Java 提交中击败了99.42%的用户

时间复杂度：O(n) 空间复杂度：O(n)，List开销

solution2：

/** * 将链表拆为2个子链表，并反转第二个子链表 * 初始链表：1->2->3->4->5->6 * * 子链表1：1->2->3 * 子链表2：4->5->6 * * 反转链表2 * 1->2->3 * 6->5->4 * * 顺序链接子链表1和子链表2 * 1->6->2->5->3->4 * * @param head */ public void reorderList2(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return; } // 定义快慢指针 slow每次走一步，fast每次走两步 ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } // slow指针前(包含slow)为链表1，slow指针后(不包含slow)为链表2，即secondHead=slow.next ListNode secondHead = slow.next; // 反转链表2 secondHead = reverseList(secondHead); // 遍历链表2，顺序链接链表1和链表2节点 while (secondHead != null){ ListNode next = secondHead.next; secondHead.next = head.next; head.next = secondHead; head = secondHead.next; secondHead = next; } // 将最后的节点.next指向null head.next = null; } /** * 反转链表 * @param head * @return */ public ListNode reverseList(ListNode head){ if (head == null) { return null; } if (head.next == null) { return head; } ListNode pre = null; while (head != null) { ListNode next = head.next; head.next = pre; pre = head; head = next; } return pre; }

执行结果： 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：41.2 MB, 在所有 Java 提交中击败了88.05%的用户

时间复杂度：O(n) 空间复杂度：O(1)