2015年9月9日星期三

Lintcode: 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.

Have you met this question in a real interview? 
Yes
Example
For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.
Tags Expand 
Linked List

Thought:
1. separate the list into two parts, remember to set the left half list points to NULL at the end
2. inverse the right half
3. insert the right half into left half

Codes Reference:
http://siddontang.gitbooks.io/leetcode-solution/content/linked_list/reorder_list.html

Time: O(n) + O(n) + O(n)
Space: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        // write your code here
        //find the middle pointer
        if(head == NULL || head->next == NULL) return;
        ListNode *slow, *fast;
        slow = fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        slow = head;
        
        //reverse nodes from middle to end 
        ListNode *prev = fast;
        ListNode *cur = prev->next;
        while(cur){
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        fast->next = NULL;
        fast = prev;
        
        //insert right half list into left half list
       while(fast){
           ListNode *temp = slow->next;
           slow->next = fast;
           ListNode *temp2 = fast->next;
           fast->next = temp;
           slow = temp;
           fast = temp2;
       }
    }
};



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        // write your code here
        if(head == NULL) return;
     ListNode *p1, *p2;
     p1 = p2 = head;
     while(p1 && p2 && p2->next && p2->next->next){
      p1 = p1->next;
      p2 = p2->next->next;
     }
     p2 = p1->next;
     p1->next = NULL;
     p1 = head;

        //reverse second half
     ListNode *prev, *cur;
     prev = NULL;
     cur = p2;
     while( cur ){
      ListNode *temp = cur->next;
      cur->next = prev;
      prev =  cur;
      cur = temp;
     }
     p2 = prev;

        //insert second half into first half
     while(p1 && p2){
      ListNode *next1 = p1->next;
            ListNode *next2 = p2->next;
            p1->next = p2;
            p2->next = next1;
            p1 = next1;
            p2 = next2; 
        }

    }
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)