Showing posts with label reverse list. Show all posts
Showing posts with label reverse list. Show all posts

Saturday, August 6, 2016

234. Palindrome Linked List

I count the total nodes first and then find the middle node. To cover both cases of odd/even number, the middle node should be the ceiling of n / 2. And then reverse the sublist starting from the middle node. After that, compare the first half list with the reversed second half list to see if any discrepancy.

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:    bool isPalindrome(ListNode* head) {  
12:      int count = countList(head);  
13:      if (count < 2) return true;  
14:      int mid = (count+1)/2;  
15:      ListNode *l2 = head;  
16:      while (mid) {  
17:        l2 = l2->next;  
18:        mid--;  
19:      }  
20:      l2 = reverseList(l2);  
21:      while (l2) {  
22:        if (head->val != l2->val) return false;  
23:        head = head->next;  
24:        l2 = l2->next;  
25:      }  
26:      return true;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while(head) {  
31:        count++;  
32:        head = head->next;  
33:      }  
34:      return count;  
35:    }  
36:    ListNode *reverseList(ListNode *head) {  
37:      ListNode *pre = NULL;  
38:      while (head) {  
39:        ListNode *next = head->next;  
40:        head->next = pre;  
41:        pre = head;  
42:        head = next;  
43:      }  
44:      return pre;  
45:    }  
46:  };  

Wednesday, August 3, 2016

206. Reverse Linked List

I had following code in first place.

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:    ListNode* reverseList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      ListNode *prev = head, *cur = head->next;  
14:      prev->next = NULL;  
15:      while (cur) {  
16:        ListNode *tmp = cur->next;  
17:        cur->next = prev;  
18:        prev = cur;  
19:        cur = tmp;  
20:      }  
21:      return prev;  
22:    }  
23:  };  

And here is the more concise one from top rated solution.

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:    ListNode* reverseList(ListNode* head) {  
12:      ListNode *prev = NULL;  
13:      while (head) {  
14:        ListNode *tmp = head->next;  
15:        head->next = prev;  
16:        prev = head;  
17:        head = tmp;  
18:      }  
19:      return prev;  
20:    }  
21:  };  

Sunday, July 17, 2016

369. Plus One Linked List

Well, I was thinking reverse the list, do increase and reverse the list again in first place. However, I don't think it is expected in the interview because this is so naive. And particularly, if we are not allowed to change the list order then this solution is out. Actually, we can do recursive way because recursion helps us "reverse" the list.

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:    ListNode* plusOne(ListNode* head) {  
12:      if (dfs(head) == 0) return head;  
13:      else {  
14:        ListNode *node = new ListNode(1);  
15:        node->next = head;  
16:        return node;  
17:      }  
18:    }  
19:    int dfs(ListNode *head) {  
20:      if (head == NULL) return 1;  
21:      int carry = dfs(head->next);  
22:      if (carry == 0) return 0;  
23:      int val = head->val + 1;  
24:      head->val = val % 10;  
25:      return val / 10;  
26:    }  
27:  };  

Sunday, July 10, 2016

25. Reverse Nodes in k-Group

The trick I noticed here is the first node of sublist will be the end of the new list and will be the new "dummy" node for the next new list. And we mustn't forget the end node's next should be updated every time we reverse the sublist.

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:    ListNode* reverseKGroup(ListNode* head, int k) {  
12:      if (k <= 1) return head;  
13:      ListNode *dummy = new ListNode(0);  
14:      dummy->next = head;  
15:      ListNode *prev = dummy, *cur = prev->next;  
16:      while (cur) {  
17:        int count = k;  
18:        while (cur && count) {  
19:          cur = cur->next;  
20:          count--;  
21:        }  
22:        if (count) break;  
23:        ListNode *end = prev->next;  
24:        ListNode *p = end->next;  
25:        while (p != cur) {  
26:          end->next = p->next;  
27:          p->next = prev->next;  
28:          prev->next = p;  
29:          p = end->next;  
30:        }  
31:        prev = end;  
32:      }  
33:      head = dummy->next;  
34:      delete dummy;  
35:      return head;  
36:    }  
37:  };  

Sunday, July 3, 2016

143. Reorder List

Three steps:
(1) cut into two lists (note the first list must be longer or equal to the second list).
(2) reverse the second list.
(3) merge the two lists.

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 == NULL || head->next == NULL) return;  
13:      int count = countList(head);  
14:      count = (count + 1) / 2;  
15:      ListNode *prev = NULL, *cur = head;  
16:      while (count) {  
17:        count--;  
18:        prev = cur;  
19:        cur = cur->next;  
20:      }  
21:      prev->next = NULL;  
22:      ListNode *l1 = head;  
23:      ListNode *l2 = reverseList(cur);  
24:      while (l2) {  
25:        ListNode *tmp = l2->next;  
26:        l2->next = l1->next;  
27:        l1->next = l2;  
28:        l1 = l2->next;  
29:        l2 = tmp;  
30:      }  
31:      return;  
32:    }  
33:    int countList(ListNode* head) {  
34:      int count = 0;  
35:      while (head) {  
36:        count++;  
37:        head = head->next;  
38:      }  
39:      return count;  
40:    }  
41:    ListNode *reverseList(ListNode *head) {  
42:      ListNode *dummy = new ListNode(-1);  
43:      ListNode *cur = head;  
44:      while (cur) {  
45:        ListNode *tmp = cur;  
46:        cur = cur->next;  
47:        tmp->next = dummy->next;  
48:        dummy->next = tmp;  
49:      }  
50:      head = dummy->next;  
51:      delete dummy;  
52:      return head;  
53:    }  
54:  };