LC-143 重排链表

原题链接

讨论澄清

这里首先要解决的一个问题就是如何找到链表的中点，关于如何找中点，这里可以利用快慢指针找中点.接下来是以中点将链表分成两部分，并将后一部分链表进行反转，之后再将反转后的链表一次插入前一个链表中，这个题目细想起来就是三个知识点融合起来：找链表中点、反转链表、将一个链表按要求插入另外一个链表，这三部分的操作都是经典的必须掌握的基础链表知识。

思路简述

首先对边界条件也就是空链表的情况加以判断，之后通过快慢指针找到链表的中点，并且将一个链表分成两个链表，之后将后一个链表反转，在之后将后一个链表的每一个元素插到前一个链表的中间，如果有多出来的未插入的情况则放在前一个链表的最末尾。

注意事项

注意这里的边界条件是链表为空的情况，要单独加以判断。

具体代码

/**
 * 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 = finMid(head);      
        //将中点之后的链表反转，先拿到中点之后的点
       ListNode l2 = mid.next;
       mid.next = null;
       l2 = reverse(l2);
       //将反转后的链表一次插入到前半段链表中
       ListNode l1 = head; 
       while(l1!=null&&l2!=null){
           ListNode next = l1.next;        
           l1.next = l2;
            l2 = l2.next;
            l1.next.next = next;
           l1 = next;
       }
    }
    //使用快慢指针的方式来实现中点节点的查询
        public ListNode finMid(ListNode head){
            //经典查询方法
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null){
                fast= fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
        //反转链表
        public ListNode reverse(ListNode head){
            ListNode newnode = null;
            ListNode next = head;
            while(head!=null){
                //经典四步判断
                next = head.next;
               head.next = newnode;
                newnode = head;
                head = next;
            }
            return newnode;
        }
}