学步园

LeetCode:Reorder List

题目（题目链接）：

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

分析：先用快慢指针找到链表的中点，然后翻转链表后半部分，再和前半部分组合。需要注意的是把链表分成两半时，前半段的尾节点要置为NULL，翻转链表时也要把尾节点置为NULL。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head == NULL || head->next == NULL)return;
        ListNode *fastp = head, *lowp = head, *tail = NULL;
        while(fastp != NULL && fastp->next != NULL)
        {//利用快慢指针找到链表的中点
            tail = lowp;
            fastp = fastp->next->next;
            lowp = lowp->next;
        }
        tail->next = NULL; //此时tail 指向前半段的结尾
        reverseList(lowp);//翻转链表后半段
        fastp = head;
        tail = NULL;
        while(fastp != NULL)
        {
            ListNode *tmp = lowp->next;
            lowp->next = fastp->next;
            fastp->next = lowp;
            tail = lowp;
            fastp = lowp->next;
            lowp = tmp;
        }
        if(lowp != NULL)
            tail->next = lowp;

    }
    void reverseList(ListNode* &head)
    {//翻转链表
        if(head == NULL || head->next == NULL)return;
        ListNode *pre = head, *p = pre->next;
        while(p != NULL)
        {
            ListNode *tmp = p->next;
            p->next = pre;
            pre = p;
            p = tmp;
        }
        head->next = NULL;
        head = pre;
    }
};

网上一般都是C++实现，自己做了个java版本，算法不同，网上也有同样算法的C++版。

代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public void reorderList(ListNode head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head==null||head.next==null||head.next.next==null) return;
        Vector<ListNode> vin=new Vector<ListNode>();
        Vector<ListNode> vout=new Vector<ListNode>();
        ListNode p=head;
        while(p!=null)
        {
            vin.add(p);
            p=p.next;
        }
        int i=0;
        int n=vin.size();
        int k=n-1;
        for(;k>n/2;i++,k--)
        {
            vout.add(vin.get(i));
            vout.add(vin.get(k));
        }
        while(i<n/2+1)
        {
            vout.add(vin.get(i));
            i++;
        }
        int j=0;
        for(;j<vout.size()-1;j++)
        {
            vout.get(j).next=vout.get(j+1);
        }
        vout.get(j).next=null;
        
    }
}