Leetcode143. 重排链表

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 

代码如下：

class Solution {public void reorderList(ListNode head) {if(head == null) {return;}ListNode slow = head;ListNode fast = head;while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;}ListNode l2 = slow.next;//分开两个链表，前半部分的链表的尾节点指向空slow.next = null;//翻转后半部分链表，如果1-2-3-4-5 翻转的是4-5，如果是1-2-3-4-5-6翻转的是4-5-6l2 = reverse(l2);ListNode l1 = head;mergeList(l1,l2);}public ListNode reverse(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode post = cur.next;cur.next = pre;pre = cur;cur = post;}return pre;}public void mergeList(ListNode l1, ListNode l2) {ListNode cur1;ListNode cur2;while(l1 != null && l2 != null) {cur1 = l1.next;cur2 = l2.next;l1.next = l2;l1 = cur1;l2.next = l1;l2 = cur2;}}
}