解题思路:
- 边界处理
- 找到中间节点
- 翻转后半段链表
- 归并链表
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null) return; ListNode mid = getMid(head); ListNode midNext = mid.next; mid.next = null; ListNode prev = null; ListNode cur = midNext; while(cur != null){ ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } ListNode node = head; while(node != null && prev != null){ ListNode n1 = node.next; ListNode n2 = prev.next; node.next = prev; prev.next = n1; node = n1; prev = n2; } } public ListNode getMid(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; } }