# 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):
"""
:rtype: ListNode
"""
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 val: int
:rtype: ListNode
"""
return None
# use dummy node to solve corner case
dummy = ListNode(-1)
previous = dummy
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):
"""
:rtype: ListNode
"""
diff = abs(l_a - l_b)

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

else:
return None

length = 0
length += 1
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
return current if current.val else current.next