首页 > 代码库 > Reorder List

Reorder List

Reorder List

           Given a singly linked list L: L0L1→…→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}.

说明:分三步,1。从中间分开,成两部分。2,后半部分链表逆置。3.插入合并。

/** * 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) {        if(head == NULL) return;         ListNode *p1, *p2, *p3, *head2;        p1 = p2 = head;        while(p2->next && p2->next->next) {            p1 = p1->next;            p2 = p2->next->next;        }        head2 = p1->next; p1 = p1->next = NULL;        p2 = head2;        while(p2) {            p3 = p2->next;            p2->next = p1;            p1 = p2;            p2 = p3;        }        head2 = p1; p1 = head;        while(head2 && p1) {            p2 = head2->next;            head2->next = p1->next;            p1->next = head2;            head2 = p2;            p1 = p1->next->next;        }                    }};