LIKE CODING: Linked List

Showing posts with label Linked List. Show all posts

Saturday, January 16, 2016

LeetCode [328] Odd Even Linked List

328. Odd Even Linked List

Medium

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Constraints:

The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...
The length of the linked list is between [0, 10^4].

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head) return NULL;
        ListNode* p = head->next;
        ListNode* t = head;
        while(p && p->next){
            ListNode* next = p->next->next;
            ListNode* c = p->next;
            c->next = t->next;
            t->next = c;
            t = c;
            p->next = next;
            p = next;
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode HO = new ListNode();
        ListNode HE = new ListNode();
        ListNode pO = HO;
        ListNode pE = HE;
        ListNode p = head;
        int i=1;
        while(p!=null){
            ListNode next = p.next;
            p.next = null;
            if(i%2==1){
                pO.next = p;
                pO = p;
            }else{
                pE.next = p;
                pE = p;
            }
            p = next;
            i++;
        }
        pO.next = HE.next;
        return HO.next;
    }
}

Wednesday, July 15, 2015

LeetCode [237] Delete Node in a Linked List

===============
Ref
[1] https://leetcode.com/problems/delete-node-in-a-linked-list/
OJ

Thursday, July 9, 2015

LeetCode [234] Palindrome Linked List

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

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

/**
 * 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) {
        ListNode *H1 = new ListNode(0);
        H1->next = head;
        ListNode *p1 = H1, *p2 = H1;
        while(p2 && p2->next){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        ListNode *H2 = new ListNode(0), *h2 = p1->next;
        H2->next = h2;
        if(!h2) return true;
        p2 = h2->next;
        h2->next = NULL;
        while(p2){
            ListNode *next = p2->next;
            p2->next = h2;
            H2->next = p2;
            h2 = p2;
            p2 = next;
        }
        
        p1 = H1;
        p2 = H2;
        while(p2){
            if(p1->val!=p2->val) return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null) return true;
        if(head.next.next==null) return head.val==head.next.val;
        
        ListNode fast = head, slow = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode prev = slow;
        ListNode cur = slow.next;
        ListNode p1 = head;
        ListNode p2 = null;
        while(cur!=null){
            ListNode next = cur.next;
            if(next==null) p2 = cur;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        
        
        while(true){
            if(p1.val!=p2.val) return false;
            if(p1.next == p2 || p1.next == p2.next) break;
            p1 = p1.next;
            p2 = p2.next;
        }
        
        return true;
    }
}

Tuesday, May 12, 2015

LeetCode [206] Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !(head->next)) return head;
        ListNode* H = new ListNode(0);
        H->next = head;
        ListNode* p = head->next;
        head->next = NULL;
        while(p)
        {
            ListNode* q = p->next;
            p->next = H->next;
            H->next = p;
            p = q;
        }
        return H->next;
    }
};

//C++: method1 14ms
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *H = new ListNode(0);
        while(head){
            ListNode *first = H->next;
            H->next = head;
            head = head->next;
            H->next->next = first;
        }
        return H->next;
    }
};
]]></script>

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: method2 12ms
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void helper(ListNode* head, ListNode* H){
        if(!head) return;
        ListNode* first = H->next;
        H->next = head;
        ListNode* next = head->next;
        H->next->next = first;
        helper(next, H);
    }

    ListNode* reverseList(ListNode* head) {
        ListNode *H = new ListNode(0);
        helper(head, H);
        return H->next;
    }
};
]]></script>

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: method3 8ms
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode H = new ListNode();
        ListNode p = head;
        while(p!=null){
            ListNode h = H.next;
            ListNode next = p.next;
            p.next = h;
            H.next = p;
            p = next;
        }
        return H.next;
    }
}

Saturday, February 21, 2015

LeetCode [160] Intersection of Two Linked Lists

160. Intersection of Two Linked Lists

Easy

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

class Solution {
public:
    ListNode *helper(ListNode *p1, ListNode *p2, ListNode *p3){
        while(p1){
            p1 = p1->next;
            p2 = p2->next;
        }
        while(p2&&p2!=p3){
            p2 = p2->next;
            p3 = p3->next;
        }
        return p2;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pa = headA, *pb = headB;
        while(pa && pb){
            pa = pa->next;
            pb = pb->next;
        }
        if(pa){
            return helper(pa, headA, headB);
        }else{
            return helper(pb, headB, headA);
        }
    }
};

Friday, February 20, 2015

LeetCode [143] 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 may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next || !head->next->next) return;
        ListNode *p1 = head, *p2 = head;
        while(p2 && p2->next && p2->next->next){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        ListNode *head2 = p1->next;
        p1->next = NULL;
        p2 = head2->next;
        head2->next = NULL;
        while(p2){
            ListNode *next = p2->next;
            p2->next = head2;
            head2 = p2;
            p2 = next;
        }
        p1 = head;
        p2 = head2;
        while(p1 && p2){
            ListNode *next1 = p1->next;
            ListNode *next2 = p2->next;
            p1->next = p2;
            p2->next = next1;
            p1 = next1;
            p2 = next2;
        }
    }
};

LeetCode [142] Linked List Cycle II

142. Linked List Cycle II

Medium

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:
Can you solve it without using extra space?

//C++: 12ms
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *p1 = head;
        ListNode *p2 = head;
        while(true){
            if(!p2||!p2->next) return NULL;
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1==p2) break;
        }
        p1 = head;
        while(p1!=p2){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};

//Java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head==null || head.next==null) return null;
        ListNode s = head, f = head;
        
        while(s!=null && f!=null && f.next!=null){
            s = s.next;
            f = f.next.next;
            if(s==f) break;
        }
        
        if(s!=f) return null;
        
        s = head;
        while(s!=f){
            s = s.next;
            f = f.next;
        }
        return s;
    }
}

LeetCode [141] Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If posis -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode *p1 = head;
        ListNode *p2 = head;
        while(p2 && p2->next){
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1==p2) return true;
        }
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode s = head;
        ListNode f = head;
        
        while(s!=null && f!=null && f.next!=null){
            s = s.next;
            f = f.next.next;
            if(s==f) return true;
        }
        
        return false;
    }
}