首页 > 代码库 > LeetCode :: Reorder List

LeetCode :: Reorder List

Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}.

其实题目的意思就是一个链表分成前后两节,以L0->L1->L2->L3->L4->L5为例,分成L0->L1->L2 以及 L3->L4->L5,然后把后面的部分倒转变成L5->L4->L3, 接着挨个插入到前一个链表中,就OK了。  思路就是这么简单,接下来看一下实现,函数Reverse是实现一个链表的反转,需要注意一下循环结束条件,以及反转时先后顺序;然后reoreder函数里,用fast、slow两个指针来找到链表的中点,从中点割开,成为两个链表。这里说一下,如果节点个数为奇数,那么结束时slow指向的刚好为中点,如果为偶数,是指向将链表均分两部分后,第一部分的尾节点,无论哪种情况,将slow->next作为后一个链表的开始都是正确的。具体实现如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *Reverse(ListNode  *head){
        if (head == NULL){
            return head;
        }    
        ListNode *pre_pos = NULL;
        ListNode *pos = head;
        ListNode *next_pos = head->next;
        
        while(next_pos != NULL){     //注意这里是next_pos
            pos->next = pre_pos;
            pre_pos = pos;
            pos = next_pos;
            next_pos = next_pos->next;
        }
        pos->next = pre_pos;
        return pos;
    }
    
    void reorderList(ListNode *head) {
        if (head == NULL)
            return;
            
        ListNode *fast, *slow, *before, *after;
        fast = slow = before = head;
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        
        after = Reverse(slow->next);
        slow->next = NULL;
        
        ListNode *insert;
        while(after != NULL){
            insert = after;
            after = after->next;
            insert->next = before->next;
            before->next = insert;
            before = insert->next;
        }
        
        return;
    }
};