Leetcode Linked List Related

January 2019 4 minute read

There are many linked list related problem on leetcode,I will write some solution here, and try to find out if there is a pattern for this kind of problem.

876. Middle of The Linked List

Solution:

Use two pointers, the fast one moves two nodes one time, slow one moves one node one time. When fast point reaches the end, the position of the slow point is at the middle of the linked list.

Corner Case:

  1. case 1 [1,2,3,4,5]

    fast : 1,3,5

    slow : 1,2,3

    return slow

  2. case 2 [1,2,3,4,5,6]

    fast : 1,3,5

    slow: 1,2,3

    return slow.next

Code:

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        fast = head
        slow = head
        while 1:
            if not fast.next:
                # case 1
                return slow
            if not fast.next.next:
                # case 2
                return slow.next

            slow = slow.next
            fast = fast.next.next

203. Remove Linked List Elements

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

Solution: Connect previous to next node if current have the value of deleting ,Use dummy node to solve corner case(the head value is the delete value).

Code:

class Solution:
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if not head:
            return None
        # use dummy node to solve corner case
        dummy = ListNode(-1)
        dummy.next = head
        previous = dummy
        current = head
        while current:
            if current.val == val:
                previous.next = current.next
            else:
                previous = previous.next
            current = current.next
        return dummy.next

160. Intersection of Two Linked Lists

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

Solution:

  1. Get count of the nodes in the first list, let count be c1.
  2. Get count of the nodes in the second list, let count be c2.
  3. Get the difference of counts d = abs(c1 – c2)
  4. Now traverse the bigger list d steps, so from here both lists have equal number of nodes.
  5. Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Code:

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        l_a = get_length(headA)
        l_b = get_length(headB)
        diff = abs(l_a - l_b)

        # move to same start position
        if l_a > l_b:
            while diff:
                headA = headA.next
                diff -= 1
        if l_a < l_b:
            while diff:
                headB = headB.next
                diff -= 1

        while headA and headB:
            if headA == headB:
                return headA
            else:
                headA = headA.next
                headB = headB.next
        return None


def get_length(head):
    length = 0
    while head:
        length += 1
        head = head.next
    return length

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Solution:

Use dummy node to solve the corner case

Code:

class Solution:
    def addTwoNumbers(self, r1: 'ListNode', r2: 'ListNode') -> 'ListNode':
        dummy = ListNode(-1)
        current = dummy
        carry = 0
        while r1 or r2:
            value = carry
            if r1:
                value += r1.val
            if r2:
                value += r2.val

            if value >= 10:
                carry = 1
                value = value % 10
            else:
                carry = 0

            if r1:
                r1 = r1.next
            if r2:
                r2 = r2.next

            current.next = ListNode(value)
            current = current.next

        if carry:
            current.next = ListNode(1)

        return dummy.next

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Solution:

Use two stacks, because stack is LIFO. Init a head node to solve corner case.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

Code:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        stack1 = list()
        stack2 = list()
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        current = ListNode(-1)
        carry = 0
        while len(stack1) or len(stack2):
            value = carry
            if len(stack1):
                value += stack1.pop()
            if len(stack2):
                value += stack2.pop()
            if value >= 10:
                carry = 1
                value = value % 10
            else:
                carry = 0
            head = ListNode(carry)
            current.val = value
            head.next = current
            current = head
        return current if current.val else current.next