143. 重排链表

给定一个单链表 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.1 快慢指针

主要是三步，举个例子。 1 -> 2 -> 3 -> 4 -> 5 -> 6 第一步，将链表平均分成两半 1 -> 2 -> 3 4 -> 5 -> 6 第二步，将第二个链表逆序 1 -> 2 -> 3 6 -> 5 -> 4 第三步，依次连接两个链表 1 -> 6 -> 2 -> 5 -> 3 -> 4

第一步找中点的话，应用 快慢指针。快指针一次走两步，慢指针一次走一步，当快指针走到终点的话，慢指针会刚好到中点。如果节点个数是偶数的话，slow 走到的是左端点，利用这一点，我们可以把奇数和偶数的情况合并，不需要分开考虑。

第二步链表逆序的话，在 第 2 题 讨论过了，有迭代和递归的两种方式，迭代的话主要利用两个指针，依次逆转。

第三步的话就很简单了，两个指针分别向后移动就可以。

上代码:

/** * 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 || head.next==null || head.next.next==null){ return ; } ListNode fast= head; ListNode slow= head; while(fast.next!=null && fast.next.next!=null){ slow=slow.next; fast=fast.next.next; } ListNode newNode = slow.next; slow.next = null; newNode = reveser(newNode); while(newNode!=null){ ListNode temp = newNode.next; newNode.next = head.next; head.next = newNode; head = newNode.next; newNode = temp; } } public ListNode reveser(ListNode p){ if(p == null){ return null ; } ListNode tail = p; p = p.next; tail.next=null; while(p!=null){ ListNode temp = p.next; p.next=tail; tail=p; p=temp; } return tail; } }