LeetCode 143.重排链表

1.题目要求将原链表重排序为第一个节点-最后一个节点-第二个节点-倒数第二个节点-第三个节点-倒数第三个节点...。2.思路以1-2-3-4-5为例。1找到链表的中间节点middleNode快慢指针法找到中间节点mid 3。2翻转后半部分的链表reverseList从中点开始反转后半部分的链表。反转后1-2-35-4-3注意3是共享节点。3交错合并两个链表的节点从前往后逐个交错合并。3.复杂度分析1时间复杂度O(n)其中n为链表的长度。2空间复杂度O(1)仅用到若干额外变量。4.疑问循环条件while head2.next为什么不能写成while head2在hot100 234.回文链表中是while(head 2!null)这里却是while(head2.next ! null)答这里不用head2 ! null是为了防止形成环 由于mid节点是重排链表后的最后一个节点因此当head2刚走到mid时1要么此时head1也指向mid此时对应于链表是奇数的情况2要么此时head1指向mid节点的前一个节点对应于链表是偶数的情况无论哪种情况都表明这个链表已经在head2刚走到mid时重排完成因此可以直接退出循环再继续循环到head2 null会形成环。附代码class Solution { public void reorderList(ListNode head) { ListNode mid middleNode(head); ListNode head2 reverseList(mid); // 这里不用head2 ! null是为了防止形成环 // 由于mid节点是重排链表后的最后一个节点 // 因此当head2刚走到mid时 // 1要么此时head1也指向mid此时对应于链表是奇数的情况 // 2要么此时head1指向mid节点的前一个节点对应于链表是偶数的情况 // 无论哪种情况都表明这个链表已经重排完成因此可以直接退出循环再继续循环下去会形成环 while(head2.next ! null){ ListNode next1 head.next; ListNode next2 head2.next; head.next head2; head2.next next1; head next1; head2 next2; } } // 876.链表的中间节点,快慢指针法 private ListNode middleNode(ListNode head){ ListNode slow head; ListNode fast head; while(fast ! null fast.next ! null){ slow slow.next; fast fast.next.next; } return slow; } // 206.反转链表 private ListNode reverseList(ListNode head){ ListNode pre null; ListNode cur head; while(cur ! null){ ListNode tmp cur.next; cur.next pre; pre cur; cur tmp; } return pre; } }ACM模式import java.util.Scanner; // 将 ListNode 定义为独立的类 class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取链表长度 int n scanner.nextInt(); // 读取链表元素 int[] nums new int[n]; for (int i 0; i n; i) { nums[i] scanner.nextInt(); } // 创建链表 ListNode head null; if (n 0) { head new ListNode(nums[0]); ListNode current head; for (int i 1; i n; i) { current.next new ListNode(nums[i]); current current.next; } } // 调用重排链表方法 Solution solution new Solution(); solution.reorderList(head); // 输出重排后的链表 if (head null) { System.out.println(); } else { ListNode current head; while (current ! null) { System.out.print(current.val); if (current.next ! null) { System.out.print( ); } current current.next; } System.out.println(); } scanner.close(); } } // 重排链表方法放在 Solution 类中 class Solution { public void reorderList(ListNode head) { if (head null || head.next null) { return; } ListNode mid middleNode(head); ListNode head2 reverseList(mid); while (head2.next ! null) { ListNode next1 head.next; ListNode next2 head2.next; head.next head2; head2.next next1; head next1; head2 next2; } } // 876. 链表的中间节点快慢指针法 private ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } // 206. 反转链表 private ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode tmp cur.next; cur.next pre; pre cur; cur tmp; } return pre; } }