Linked List

Singly-Linked List

• get i-th element - O(n)
• insert - O(1)
• delete - O(n)
• search - O(n)
  (To achieve delete purpose, we need to find pre and next, next can be found by reference, while pre needs to traverse whole list )

Doubly-Linked List

• get i-th element - O(n)
• insert - O(1)
• delete - O(1)
• search - O(n)

when using add or delete operations, use linked list.
when using access operation, use array.

Two-Pointer in Linked List - O(n)

Problem: given a linked list, determine if it has a cycle of it

1. hash map
   • can be done by traversing list, then determine cycle inside when there is repeating item - take O(n) may not efficient
2. two-pointer
   • two pointer can be slow and fast, fast pointer is one more step than slow pointer
   • if there is cycle, then fast and slow pointers can meet.
   • if there is no cycle, then fast and slow pointers can not meet, fast pointer will stop at the end of list.

Solution(answer by #2)

public boolean hasCycle(ListNode head) {
    /** declare two pointers reference to head node */
    ListNode fast = head;
    ListNode slow = head;

    while (fast != null && fast.next != null){
        slow = slow.next;
        /** fast pointer move one more step than slow pointer */
        fast = fast.next.next;
        /** check if two pointers meet */
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

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

Solution(answer by #1)

def detectCycle(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    s = set();
    while (head and head.next):
        if (head not in s):
            s.add(head)
        else:
            return head
        head = head.next

Solution(answer by #2)

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        /** check cycle inside */
        if (fast == slow) {
            break;
        }
    }
    /** if there is one element or empty in list */
    if (fast == null || fast.next == null) {
        return null;
    }
    /** declare new pointer to track */
    ListNode slow2 = head;
    while (slow2 != fast) {
        slow2 = slow2.next;
        fast = fast.next;
    }
    return slow2;
}

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

Solution(answe by #1)

def getIntersectionNode(headA, headB):
    """
    :type head1, head1: ListNode
    :rtype: ListNode
    """
    s = set()
    while (headA):
        if (headA not in s):
            s.add(headA)
        headA = headA.next
    while (headB):
        if (headB in s):
            return headB
        headB = headB.next

Problem: Given a linked list, remove the n-th node from the end of list and return its head.

Solution(answer by #1)

def removeNthFromEnd(head, n):
    """
    :type head: ListNode
    :type n: int
    :rtype: ListNode
    """
    fast = head
    slow = head
    # move fast pointer n steps more 
    while (n > 0):
        fast = fast.next
        n = n - 1
    # if there is one element in list, only can remove 0th
    if fast == None:
        head = head.next 
        return head
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head

Solution#2

/** remove from start */
public ListNode removeNthFromEnd(ListNode head, int n) {
    int size = 0;
    ListNode p = head;
    while (p !=null) {
        size++;
        p = p.next;
    }
    /** declare nth from start */
    int fromStart = size - n + 1;
    /** if remove first node */
    if (fromStart == 1) {
        return head = head.next;
    }
    p = head;
    int i = 0;
    while (p != null) {
        i++;
        if (i == fromStart-1) {
            p.next = p.next.next;
        }
        p = p.next;
    }
    return head;
}     

Problem: Reverse a singly linked list.

Solution(answer by #2 using iteration)

public ListNode reverseList(ListNode head) {
    /** check if there is only one element or empty */
    if (head == null || head.next == null) {
        return head;
    }
    ListNode reverseList = head;
    ListNode todoList = head.next;

    reverseList.next = null;
    while (todoList != null) {
        ListNode tmp = todoList;
        todoList = todoList.next;            
        tmp.next = reverseList;
        reverseList = tmp;
    }
    return reverseList;
}

Solution(answe by #2 using recurision)

Problem: Remove all elements from a linked list of integers that have value val.