reorder list

reorder list

easy problem

A lot of problems in leetcode help us to pratice some basic skills.This problem is not hard, just cut it into three parts and solve one by one.

  • Find the midpoint of the list.
  • Reverse the second half of the list.
  • Connect the elements one by one.

Mistakes

  • Finding the midpoint, mind where the fast and slowpointer start.
  • Reverse the list, do not forget the first element.

code

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     void reorderList(ListNode *head) {
12         if ( !head || !head->next || !head->next->next ) {
13             return;
14         }
15         ListNode* slow = head;
16         ListNode* fast = head;
17         while( fast->next && fast->next->next ) {
18             fast = fast->next->next;
19             slow = slow->next;
20         }
21         fast = slow->next;
22         slow->next = NULL;
23         slow = head;
24         ListNode* p = fast->next;
25         ListNode* q = NULL;
26         fast->next = NULL;
27         while ( p ) {
28             q = p->next;
29             p ->next = fast;
30             fast = p;
31             p = q;
32         }
33         head = slow;
34         slow = slow->next;
35         head->next = NULL;
36         p = head;
37         int i = 0;
38         while ( slow && fast ) {
39             if ( i%2 ) {
40                 p->next = slow;
41                 slow = slow->next;
42             } else {
43                 p->next = fast;
44                 fast = fast->next;
45             }
46             i++;
47             p = p->next;
48         }
49         if ( slow ) {
50             p->next = slow;
51         }
52         if ( fast ) {
53             p->next = fast;
54         }
55     }
56 };
Loading Disqus comments...
Table of Contents