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:**

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

fast : 1,3,5

slow : 1,2,3

return slow

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:**

- Get count of the nodes in the first list, let count be c1.
- Get count of the nodes in the second list, let count be c2.
- Get the difference of counts d = abs(c1 – c2)
- Now traverse the bigger list d steps, so from here both lists have equal number of nodes.
- 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
```