【力扣】重排链表

一、题目形貌

题目链接： . - 力扣（LeetCode）
二、解题思绪

• 找到链表的中心节点，将链表分为两部分（可使用快慢双指针）
  
• 将后半部分链表逆序（双指针或头插法）
  
• 合并两个链表
  

一定要留意给分开之后的两个链表的末尾节点 .next 置为 null，否则会出错（超出时间限制）！
三、代码

1. class Solution {
2.     public void reorderList(ListNode head) {
3.         if(head == null || head.next == null || head.next.next == null) {
4.             return;
5.         }
6.         //1、找到链表的中间节点
7.         ListNode slow = head, fast = head;
8.         while(fast != null && fast.next != null) {
9.             slow = slow.next;
10.             fast = fast.next.next;
11.         }
12.         //此时slow所指即为中间节点
13.         //将原始链表分为两个链表,要注意给分开之后的两个链表的末尾节点.next置为空
14.         //2、逆序slow之后的部分（双指针）
15.         ListNode prev = slow.next;
16.         slow.next = null;
17.         ListNode cur = prev.next;
18.         prev.next = null;
19.         while(cur != null) {
20.             ListNode next = cur.next;
21.             cur.next = prev;
22.             prev = cur;
23.             cur = next;
24.         }
25.         //逆序之后，prev指向逆序后链表的首节点
26.         //3、合并两个链表
27.         ListNode cur1 = head, cur2 = prev;
28.         ListNode ret = new ListNode(0);
29.         ListNode ccur = ret;
30.         while(cur1 != null) {
31.             ccur.next = cur1;
32.             ccur = cur1;
33.             cur1 = cur1.next;
34.             if(cur2 != null) {
35.                 ccur.next = cur2;
36.                 ccur = cur2;
37.                 cur2 = cur2.next;
38.             }
39.         }
40.     }
41. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。