题干

给定一个单链表 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.

想法

这题本质就是前半段和后半段的逆序融合 1.通过快慢指针找到中点，注意找到的中点的下一个点才是后半段（即需要反转的点 2.反转后半部分 3.合并两个部分

其中代码需要注意的是： 首先找到了mid，要先断开mid到mid.next那条边，不然会出现环冲突

Java代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList(ListNode head) { if(head==null){ return ; } ListNode mid=findMiddle(head); ListNode h1=head; ListNode h2=mid.next; mid.next=null; h2=reverse(h2); merge(h1,h2); } public ListNode findMiddle(ListNode head){ ListNode fast=head; ListNode slow=head; while(fast.next!=null&&fast.next.next!=null){ fast=fast.next.next; slow=slow.next; } return slow; } public ListNode reverse(ListNode head){ ListNode pre=null; ListNode cur=head; while (cur!=null){ ListNode tem=cur.next; cur.next=pre; pre=cur; cur=tem; } return pre; } public void merge(ListNode h1,ListNode h2){ ListNode tem1; ListNode tem2; while(h1!=null&&h2!=null){ tem1=h1.next; tem2=h2.next; h1.next=h2; h1=tem1; h2.next=h1; h2=tem2; } } }

我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode