重排链表

题目：重排链表

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

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

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

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

示例：

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

 

题解

方案一：用List存储节点，利用双指针，按规则重新排列

class Solution2 {
    public void reorderList(ListNode head) {
        List<ListNode> list=new ArrayList<>();
        ListNode temp=head;

        while(temp!=null) {
            list.add(temp);
            temp=temp.next;
        }
        if(list.size()<=2) return;
        int i,j;
        ListNode tempH, tempL;
        for(i=0, j=list.size()-1;i<j; i++,j--) {
            tempH=list.get(i);
            tempL=list.get(j);
            temp=tempH.next;
            tempH.next=tempL;
            tempL.next=temp;
        }
        temp.next=null;
    }
}

方法二：每次找到尾结点，插入到头结点的下一个

class Solution1 {
    public ListNode end(ListNode root)
    {
        ListNode pre=root;
        root=root.next;
        while (root.next!=null)
        {
            pre=root;
            root=root.next;
        }
        pre.next=null;
        return root;
    }

    public void dfs(ListNode root)
    {
        if(root.next==null||root==null) return;
        ListNode p=end(root);
        p.next=root.next;
        root.next=p;

        dfs(p.next);
    }
    public void reorderList(ListNode head) {
        dfs(head);
    }
}

方法三：优雅的递归

class Solution {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        ListNode mid=middle(head);
        ListNode p=head;
        ListNode q=mid.next;
        q=reverse(q);
        merge(p, q);
    }

    public ListNode middle(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;
    }

    public ListNode reverse(ListNode head)
    {
        if(head==null||head.next==null)
            return head;
        ListNode newHead=reverse(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }

    public void merge(ListNode left, ListNode right)
    {
        ListNode p,q;
        while (left!=null&&right!=null)
        {
            p=left.next;
            q=right.next;

            left.next=right;
            left=p;

            right.next=left;
            right=q;
        }
    }
}