Palindrome Linked List and Sort List

Palindrome Linked List:

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

###Solution in C++:

The basic idea to solve this problem is to break this solution into 3 steps:

Step 1: Find the middle point of the whole linked list.

Step 2: Reverse the second part of the linked list and do it.

Step 3:

The fans of Linus may start shoutting: “Talk is cheap, show me the code!” Well, the code is presented below:

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL) return true;
        
        ListNode *fast = head->next, *slow = head;
        while(fast != NULL && fast->next != NULL ){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *laterList = reverseList(slow->next);
        slow->next = NULL;
        while(laterList && head){
            if(laterList->val != head->val){
                return false;
            }else{
                laterList = laterList->next;
                head = head->next;
            }
        }
        return true;
    }
    
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        while(head != NULL && head->next != NULL){
            ListNode* next = head->next->next;
            head->next->next = dummy->next;
            dummy->next = head->next;
            head->next = next;
        }
        ListNode* key = dummy->next;
        delete dummy;
        return key;
    }
};

If you use 

1
ListNode *fast = head, *slow = head;

Then the

1
ListNode *laterList = reverseList(slow->next);

should be modified as 

1
ListNode *laterList = reverseList(slow);

Sort List

Given a singly-linked list, sort it in a ascending order.

###Solution in C++:

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *slow = head, *fast = head;
        while(fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *l2 =slow->next;
        slow->next = NULL;
        return merge(sortList(head), sortList(l2));
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        ListNode * dummy = new ListNode(-1);
        ListNode * p = dummy;
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                p->next = l1;
                l1 = l1->next;
            }else{
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if(l1 == NULL) p->next = l2;
        if(l2 == NULL) p->next = l1;
        return dummy->next;
     }
};