Linked List

No. 234 Palindrome Linked List

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head;
    ListNode* fast = head->next;

    //find midlle of the list
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    //revert the list
    ListNode* prev = slow;
    ListNode* p = slow->next;
    slow->next = nullptr; 

    while (p)
    {
        ListNode* tmp = p->next;
        p->next = prev;
        prev = p;
        p = tmp;
    }

    //judge is palindrome
    ListNode* l = head;
    ListNode* r = prev;
    while (l && r)
    {
        if (l->val != r->val)
            return false;
        l = l->next;
        r = r->next;
    }

    return true;
}

83. Remove Duplicates from Sorted List

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* ptr = head;
        int tmp = head->val;
        while (ptr->next) {
            if (tmp == ptr->next->val) {
                ListNode* temp = ptr->next;
                ptr->next = ptr->next->next;
                delete temp;
            } else {
                tmp = ptr->next->val;
                ptr = ptr->next;
            }
        }
        return head;
    }
};

141. Linked List Cycle

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *p1= head, *p2= head;
        while (p1 && p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
            if (p1==p2) return true;
        }
        return false;
    }
};

142. Linked List Cycle II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *p1=head,*p2=head,*p=NULL;
        while(p2 && p2->next)
        {
            p1= p1->next;
            p2= p2->next->next;
            if(p1== p2)   /* find cycle*/
            {
                p2= head; /* head and p1 have the same distance from the cycle begins*/
                while(p2!=p1) /* find the cycle begin node if p1==p2*/
                {
                    p1= p1->next;
                    p2= p2->next;
                }
                p= p1;
                break;
            }
        }
        return p;
    }
};

21. Merge Two Sorted Lists

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode* head = new ListNode(0);
        ListNode* ptr = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                ptr->next = l1;
                l1 = l1->next;
                ptr = ptr->next;
            }
            else {
                ptr->next = l2;
                l2 = l2->next;
                ptr = ptr->next;
            }
        }
        if (l1 == NULL) ptr->next = l2;
        if (l2 == NULL) ptr->next = l1;
        return head->next;
    }
};

23. Merge k Sorted Lists

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int list_size = lists.size();
        if (list_size == 0) return NULL;
        ListNode* p = lists[0];
        while(list_size > 1) {
            int val = list_size / 2;
            int rem = list_size % 2;
            for (int i = 0; i < val; ++i) {
                lists[i] = mergeTwoLists(lists[2*i], lists[2*i+1]);
            }
            if (rem == 1) {
                lists[val] = lists[list_size-1];
            }
            list_size = val + rem;
        }
        return lists[0];
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode* head = new ListNode(0);
        ListNode* ptr = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                ptr->next = l1;
                l1 = l1->next;
                ptr = ptr->next;
            }
            else {
                ptr->next = l2;
                l2 = l2->next;
                ptr = ptr->next;
            }
        }
        if (l1 == NULL) ptr->next = l2;
        if (l2 == NULL) ptr->next = l1;
        return head->next;
    }
};








		
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s