taixingbi/*linked list.py

## *linked list.py
237. Delete Node in a Linked List
https://leetcode.com/problems/delete-node-in-a-linked-list/description/
class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        if not node:    return
        node.val= node.next.val
        node.next= node.next.next


Reverse : 206/ 92
https://leetcode.com/problems/reverse-linked-list/description/
206. Reverse Linked List
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #------------------------------------------------------------------
        #runtime complexity O(n)  space complexity O(2)
        pre= None
        while head:
            cur = head
            head = head.next

            cur.next = pre
            pre = cur
        return pre
        #------------------------------hash-----------------------------------
        #runtime complexity O(2*n)  space complexity O(n)
        l = []
        p = head
        while p:
            l.append(p.val)
            p = p.next

        p = head
        while p:
            p.val = l.pop()
            p= p.next
        return head
        #----------------------recursion-----------------------------------
        def Reverse(cur, prev=None):
            if not cur:    return prev

            n = cur.next
            cur.next = prev
            return Reverse(n, cur)

        return Reverse(head)

92. Reverse Linked List II
https://leetcode.com/problems/reverse-linked-list-ii/description/
not sovled


* 86. Partition List
https://leetcode.com/problems/partition-list/submissions/
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        #----------------------------two pointers--------------------------
        #runtime complexity O(n)
        d1= n1= ListNode(None)
        d2= n2= ListNode(None)

        while head:
            if head.val < x:
                n1.next= head
                n1= n1.next
            else:
                n2.next= head
                n2= n2.next
            head= head.next

        n2.next= None
        n1.next= d2.next

        return d1.next


## copy linked list.py
138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/description/
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """

        #------------------hash map----------------------
        #runtime complexity O(2*n)  space complexity O(n)
        # d[ original node ] = new node
        d= {}
        m=n=head
        while (m):
            d[m] = RandomListNode( m.label)
            m = m.next

        while (n):
            d[n].next= d.get(n.next)
            d[n].random= d.get(n.random)
            n= n.next

        return d.get(head)

133. Clone Graph
https://leetcode.com/problems/clone-graph/description/
# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):

        #---------------------hash map ---bfs-------------------------
        # d[ originalNode.label]= newNode
        # d[ originalNode.label].neighbors.append( newNeighbors.label )

        if not node:    return node

        root = UndirectedGraphNode(node.label)
        d = {node.label: root} #####

        nodes = [node]
        while nodes:
            nextNodes= []
            for node in nodes:
                for nei in node.neighbors:
                    if nei.label not in d:
                        nextNodes.append(nei)
                        d[nei.label] = UndirectedGraphNode(nei.label)  ######

                    d[node.label].neighbors.append(d[nei.label]) #link neighbor

            nodes= nextNodes
        return root

## double linedin.java
146. LRU Cache
https://leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

import java.util.*;

class Node {
	int value;
	int key;
	Node prev;
	Node next;
	public Node() {}

	public Node(int key, int value) {
	    this.key = key;
	    this.value = value;
	    this.prev = null;
	    this.next = null;
	}
}

class DoublyLinkedList {
	Node head;
	Node tail;

	public DoublyLinkedList() {
		head = new Node();
	    tail = new Node();
	    this.head.next = this.tail;
	    this.tail.prev = head;
	}

	public void insertHead(Node n) {
	    n.prev = head;
	    n.next = head.next;
	    head.next.prev = n;
	    head.next = n;
	}

	public void remove(Node n) {
	    n.prev.next = n.next;
	    n.next.prev = n.prev;
	}

	public int removeTail() {
	    Node n = tail.prev;
	    int key = n.key;
	    remove(n);

	    return key;
	}
}

class LRUCache {
	Map<Integer,Node> cache;
	DoublyLinkedList list;
	int capacity;

	public LRUCache(int capacity) {
		this.capacity = capacity;
	    this.cache = new HashMap<>();
	    this.list = new DoublyLinkedList();
	}

	public int get(int key) {
		if (!cache.containsKey(key))
	        return -1;

	    update(key, cache.get(key));
	    return cache.get(key).value;
	}

	public void put(int key, int value) {
		Node n = new Node(key, value);

	    if (cache.containsKey(key))
	      list.remove(cache.get(key));
	    else if (cache.size() >= capacity) {
	        int k = list.removeTail();
	        cache.remove(k);
	    }

	    list.insertHead(n);
	    cache.put(key, n);
	}

	private void update(int key, Node n) {
	    list.remove(n);
	    list.insertHead(n);
	    cache.put(key, n);
	}
}

## other.py
114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        #-------------------recursion in place-----------
        self.prev = None

        def dfs(root):
            if not root: return None

            dfs(root.right)
            dfs(root.left)

            root.right = self.prev
            root.left = None
            self.prev = root

        dfs(root)

## remove.py
83. Remove Duplicates from Sorted List
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if not head or not head.next:  return head

        n= head
        while n.next:
            if n.val==n.next.val:
                n.next= n.next.next
            else:   n= n.next
        return head

82. Remove Duplicates from Sorted List II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next: return head

        dummy= pre= ListNode(None)
        dummy.next = head

        while head and head.next:
            if head.val == head.next.val:
                while head and head.next and head.val== head.next.val:
                    head= head.next

                head= head.next
                pre.next= head

            else:
                pre= pre.next
                head= head.next

        return dummy.next

## two linked list.py
21. Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/description/
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        #-----------------------iteration--------------------------
        #runtime complexity: O(m+n)  space complexity O(1)
        dummy= cur= ListNode(None)
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next= l1
                l1= l1.next
            else:
                cur.next= l2
                l2= l2.next
            cur= cur.next

        cur.next= l1 or l2

        return dummy.next
        #-----------------------recursion--------------------------
        #runtime complexity: O(m+n)  space complexity O(m+n)
        if not l1 or not l2:    return l1 or l2

        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2


    23. Merge k Sorted Lists
    Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
    Example:
    Input:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            #-----------sorted queue-----------------
            # time complexity O(n) space complexity O(n) n is all nodes in lists
            dummy= cur= ListNode(None)

            q= [ (l.val, l) for l in lists if l]
            while q:
                q.sort()

                node= q.pop(0)[1] # linked node with smallest val
                if node.next: q.append( (node.next.val, node.next) )

                cur.next= node
                cur= cur.next

            return dummy.next

2. Add Two Numbers
https://leetcode.com/problems/add-two-numbers/description/
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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        #-----------------------------linked add-------------
        #runtime complexity: O(n) n= max( len(l1), len(l2) ) +1
        dummy= n= ListNode(None)
        carry= 0
        while l1 or l2 or carry:
            if l1:
                v1= l1.val
                l1= l1.next
            else: v1= 0

            if l2:
                v2= l2.val
                l2= l2.next
            else: v2= 0

            n.next= ListNode( (v1+v2+carry)%10 )
            n= n.next

            carry= (v1+v2+carry)/10

        return dummy.next

445. Add Two Numbers II
https://leetcode.com/problems/add-two-numbers-ii/description/
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        #runtime complexity O(m+n+max(m,n)+1) space complexity O(max(m,n))
        def linked2num(l):
            digits= []
            while l:
                digits.append(l.val)
                l= l.next
            digits.reverse()
            return sum( d*(10**i) for i, d in enumerate(digits) )

        n= linked2num(l1) + linked2num(l2)

        dummy= node= ListNode(0)
        if n==0: return node

        num= []
        while n:
            num.append(n%10)
            n /= 10

        while num:
            node.next= ListNode(num.pop())
            node=node.next
        return dummy.next


160. Intersection of Two Linked Lists
https://leetcode.com/problems/intersection-of-two-linked-lists/description/
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        #-------------------two points---------------------------------------
        #runtime complexity: O(m+n)  space complexity: O(1)
        if not headA or not headB:  return None

        pa = headA # 2 pointers
        pb = headB

        while pa!=pb:
            # if either pointer hits the end, switch head and continue the second traversal,
            # if not hit the end, just move on to next
            pa= pa.next if pa else headB
            pb= pb.next if pb else headA

        return pa # # only 2 ways to get out of the loop, they meet or the both hit the end=None
        return pb

        #------------------------------------------------------------------
        def len(head):
            cnt = 0
            while head:
                head = head.next
                cnt += 1
            return cnt

        lenA, lenB = len(headA), len(headB)
        if lenA < lenB: #headA is always longer than headB
            headA , headB = headB , headA

        offset = abs(lenA-lenB)

        while offset:
            headA= headA.next
            offset -= 1

        while headA and headB:
            if id(headA) == id(headB):  return headA

            headA = headA.next
            headB = headB.next

        return None

141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/description/
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        #---------------------two node-----------------------------------
        slow = fast = head
        while fast and fast.next:
            slow= slow.next
            fast= fast.next.next
            if slow==fast:    return True

        return False

        #-----------------------hash---------------------------------
        #runtime complexity: O(n) n=len(nodes)  space complexity: O(n)
        d= collections.defaultdict(int)
        while head:
            if d[head]: return True
            d[head]= True
            head = head.next
        return False
	237. Delete Node in a Linked List
	https://leetcode.com/problems/delete-node-in-a-linked-list/description/
	class Solution(object):
	def deleteNode(self, node):
	"""
	:type node: ListNode
	:rtype: void Do not return anything, modify node in-place instead.
	"""
	if not node: return
	node.val= node.next.val
	node.next= node.next.next


	Reverse : 206/ 92
	https://leetcode.com/problems/reverse-linked-list/description/
	206. Reverse Linked List
	class Solution(object):
	def reverseList(self, head):
	"""
	:type head: ListNode
	:rtype: ListNode
	"""
	#------------------------------------------------------------------
	#runtime complexity O(n) space complexity O(2)
	pre= None
	while head:
	cur = head
	head = head.next

	cur.next = pre
	pre = cur
	return pre
	#------------------------------hash-----------------------------------
	#runtime complexity O(2*n) space complexity O(n)
	l = []
	p = head
	while p:
	l.append(p.val)
	p = p.next

	p = head
	while p:
	p.val = l.pop()
	p= p.next
	return head
	#----------------------recursion-----------------------------------
	def Reverse(cur, prev=None):
	if not cur: return prev

	n = cur.next
	cur.next = prev
	return Reverse(n, cur)

	return Reverse(head)

	92. Reverse Linked List II
	https://leetcode.com/problems/reverse-linked-list-ii/description/
	not sovled


	* 86. Partition List
	https://leetcode.com/problems/partition-list/submissions/
	Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
	You should preserve the original relative order of the nodes in each of the two partitions.
	Example:
	Input: head = 1->4->3->2->5->2, x = 3
	Output: 1->2->2->4->3->5

	# Definition for singly-linked list.
	# class ListNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.next = None

	class Solution(object):
	def partition(self, head, x):
	"""
	:type head: ListNode
	:type x: int
	:rtype: ListNode
	"""
	#----------------------------two pointers--------------------------
	#runtime complexity O(n)
	d1= n1= ListNode(None)
	d2= n2= ListNode(None)

	while head:
	if head.val < x:
	n1.next= head
	n1= n1.next
	else:
	n2.next= head
	n2= n2.next
	head= head.next

	n2.next= None
	n1.next= d2.next

	return d1.next
	138. Copy List with Random Pointer
	https://leetcode.com/problems/copy-list-with-random-pointer/description/
	A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
	Return a deep copy of the list.

	# Definition for singly-linked list with a random pointer.
	# class RandomListNode(object):
	# def __init__(self, x):
	# self.label = x
	# self.next = None
	# self.random = None

	class Solution(object):
	def copyRandomList(self, head):
	"""
	:type head: RandomListNode
	:rtype: RandomListNode
	"""

	#------------------hash map----------------------
	#runtime complexity O(2*n) space complexity O(n)
	# d[ original node ] = new node
	d= {}
	m=n=head
	while (m):
	d[m] = RandomListNode( m.label)
	m = m.next

	while (n):
	d[n].next= d.get(n.next)
	d[n].random= d.get(n.random)
	n= n.next

	return d.get(head)

	133. Clone Graph
	https://leetcode.com/problems/clone-graph/description/
	# Definition for a undirected graph node
	# class UndirectedGraphNode:
	# def __init__(self, x):
	# self.label = x
	# self.neighbors = []

	class Solution:
	# @param node, a undirected graph node
	# @return a undirected graph node
	def cloneGraph(self, node):

	#---------------------hash map ---bfs-------------------------
	# d[ originalNode.label]= newNode
	# d[ originalNode.label].neighbors.append( newNeighbors.label )

	if not node: return node

	root = UndirectedGraphNode(node.label)
	d = {node.label: root} #####

	nodes = [node]
	while nodes:
	nextNodes= []
	for node in nodes:
	for nei in node.neighbors:
	if nei.label not in d:
	nextNodes.append(nei)
	d[nei.label] = UndirectedGraphNode(nei.label) ######

	d[node.label].neighbors.append(d[nei.label]) #link neighbor

	nodes= nextNodes
	return root
	146. LRU Cache
	https://leetcode.com/problems/lru-cache/
	Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

	get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
	put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
	it should invalidate the least recently used item before inserting a new item.
	Follow up:
	Could you do both operations in O(1) time complexity?
	Example:
	LRUCache cache = new LRUCache( 2 /* capacity */ );
	cache.put(1, 1);
	cache.put(2, 2);
	cache.get(1); // returns 1
	cache.put(3, 3); // evicts key 2
	cache.get(2); // returns -1 (not found)
	cache.put(4, 4); // evicts key 1
	cache.get(1); // returns -1 (not found)
	cache.get(3); // returns 3
	cache.get(4); // returns 4

	import java.util.*;

	class Node {
	int value;
	int key;
	Node prev;
	Node next;
	public Node() {}

	public Node(int key, int value) {
	this.key = key;
	this.value = value;
	this.prev = null;
	this.next = null;
	}
	}

	class DoublyLinkedList {
	Node head;
	Node tail;

	public DoublyLinkedList() {
	head = new Node();
	tail = new Node();
	this.head.next = this.tail;
	this.tail.prev = head;
	}

	public void insertHead(Node n) {
	n.prev = head;
	n.next = head.next;
	head.next.prev = n;
	head.next = n;
	}

	public void remove(Node n) {
	n.prev.next = n.next;
	n.next.prev = n.prev;
	}

	public int removeTail() {
	Node n = tail.prev;
	int key = n.key;
	remove(n);

	return key;
	}
	}

	class LRUCache {
	Map<Integer,Node> cache;
	DoublyLinkedList list;
	int capacity;

	public LRUCache(int capacity) {
	this.capacity = capacity;
	this.cache = new HashMap<>();
	this.list = new DoublyLinkedList();
	}

	public int get(int key) {
	if (!cache.containsKey(key))
	return -1;

	update(key, cache.get(key));
	return cache.get(key).value;
	}

	public void put(int key, int value) {
	Node n = new Node(key, value);

	if (cache.containsKey(key))
	list.remove(cache.get(key));
	else if (cache.size() >= capacity) {
	int k = list.removeTail();
	cache.remove(k);
	}

	list.insertHead(n);
	cache.put(key, n);
	}

	private void update(int key, Node n) {
	list.remove(n);
	list.insertHead(n);
	cache.put(key, n);
	}
	}
	114. Flatten Binary Tree to Linked List
	Given a binary tree, flatten it to a linked list in-place.
	For example, given the following tree:
	1
	/ \
	2 5
	/ \ \
	3 4 6
	The flattened tree should look like:
	1
	\
	2
	\
	3
	\
	4
	\
	5
	\
	6


	# Definition for a binary tree node.
	# class TreeNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None

	class Solution(object):
	def flatten(self, root):
	"""
	:type root: TreeNode
	:rtype: void Do not return anything, modify root in-place instead.
	"""
	#-------------------recursion in place-----------
	self.prev = None

	def dfs(root):
	if not root: return None

	dfs(root.right)
	dfs(root.left)

	root.right = self.prev
	root.left = None
	self.prev = root

	dfs(root)
	21. Merge Two Sorted Lists
	https://leetcode.com/problems/merge-two-sorted-lists/description/
	Input: 1->2->4, 1->3->4
	Output: 1->1->2->3->4->4
	# Definition for singly-linked list.
	# class ListNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.next = None

	class Solution(object):
	def mergeTwoLists(self, l1, l2):
	"""
	:type l1: ListNode
	:type l2: ListNode
	:rtype: ListNode
	"""
	#-----------------------iteration--------------------------
	#runtime complexity: O(m+n) space complexity O(1)
	dummy= cur= ListNode(None)
	while l1 and l2:
	if l1.val <= l2.val:
	cur.next= l1
	l1= l1.next
	else:
	cur.next= l2
	l2= l2.next
	cur= cur.next

	cur.next= l1 or l2

	return dummy.next
	#-----------------------recursion--------------------------
	#runtime complexity: O(m+n) space complexity O(m+n)
	if not l1 or not l2: return l1 or l2

	if l1.val < l2.val:
	l1.next = self.mergeTwoLists(l1.next, l2)
	return l1
	else:
	l2.next = self.mergeTwoLists(l1, l2.next)
	return l2


	23. Merge k Sorted Lists
	Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
	Example:
	Input:
	[
	1->4->5,
	1->3->4,
	2->6
	]
	Output: 1->1->2->3->4->4->5->6
	# Definition for singly-linked list.
	# class ListNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.next = None

	class Solution(object):
	def mergeKLists(self, lists):
	"""
	:type lists: List[ListNode]
	:rtype: ListNode
	"""
	#-----------sorted queue-----------------
	# time complexity O(n) space complexity O(n) n is all nodes in lists
	dummy= cur= ListNode(None)

	q= [ (l.val, l) for l in lists if l]
	while q:
	q.sort()

	node= q.pop(0)[1] # linked node with smallest val
	if node.next: q.append( (node.next.val, node.next) )

	cur.next= node
	cur= cur.next

	return dummy.next

	2. Add Two Numbers
	https://leetcode.com/problems/add-two-numbers/description/
	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.
	Example:
	Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
	Output: 7 -> 0 -> 8
	Explanation: 342 + 465 = 807.
	# Definition for singly-linked list.
	# class ListNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.next = None

	class Solution(object):
	def addTwoNumbers(self, l1, l2):
	"""
	:type l1: ListNode
	:type l2: ListNode
	:rtype: ListNode
	"""
	#-----------------------------linked add-------------
	#runtime complexity: O(n) n= max( len(l1), len(l2) ) +1
	dummy= n= ListNode(None)
	carry= 0
	while l1 or l2 or carry:
	if l1:
	v1= l1.val
	l1= l1.next
	else: v1= 0

	if l2:
	v2= l2.val
	l2= l2.next
	else: v2= 0

	n.next= ListNode( (v1+v2+carry)%10 )
	n= n.next

	carry= (v1+v2+carry)/10

	return dummy.next

	445. Add Two Numbers II
	https://leetcode.com/problems/add-two-numbers-ii/description/
	class Solution(object):
	def addTwoNumbers(self, l1, l2):
	"""
	:type l1: ListNode
	:type l2: ListNode
	:rtype: ListNode
	"""
	#runtime complexity O(m+n+max(m,n)+1) space complexity O(max(m,n))
	def linked2num(l):
	digits= []
	while l:
	digits.append(l.val)
	l= l.next
	digits.reverse()
	return sum( d(10*i) for i, d in enumerate(digits) )

	n= linked2num(l1) + linked2num(l2)

	dummy= node= ListNode(0)
	if n==0: return node

	num= []
	while n:
	num.append(n%10)
	n /= 10

	while num:
	node.next= ListNode(num.pop())
	node=node.next
	return dummy.next


	160. Intersection of Two Linked Lists
	https://leetcode.com/problems/intersection-of-two-linked-lists/description/
	A: a1 → a2
	↘
	c1 → c2 → c3
	↗
	B: b1 → b2 → b3
	class Solution(object):
	def getIntersectionNode(self, headA, headB):
	"""
	:type head1, head1: ListNode
	:rtype: ListNode
	"""
	#-------------------two points---------------------------------------
	#runtime complexity: O(m+n) space complexity: O(1)
	if not headA or not headB: return None

	pa = headA # 2 pointers
	pb = headB

	while pa!=pb:
	# if either pointer hits the end, switch head and continue the second traversal,
	# if not hit the end, just move on to next
	pa= pa.next if pa else headB
	pb= pb.next if pb else headA

	return pa # # only 2 ways to get out of the loop, they meet or the both hit the end=None
	return pb

	#------------------------------------------------------------------
	def len(head):
	cnt = 0
	while head:
	head = head.next
	cnt += 1
	return cnt

	lenA, lenB = len(headA), len(headB)
	if lenA < lenB: #headA is always longer than headB
	headA , headB = headB , headA

	offset = abs(lenA-lenB)

	while offset:
	headA= headA.next
	offset -= 1

	while headA and headB:
	if id(headA) == id(headB): return headA

	headA = headA.next
	headB = headB.next

	return None

	141. Linked List Cycle
	https://leetcode.com/problems/linked-list-cycle/description/
	class Solution(object):
	def hasCycle(self, head):
	"""
	:type head: ListNode
	:rtype: bool
	"""
	#---------------------two node-----------------------------------
	slow = fast = head
	while fast and fast.next:
	slow= slow.next
	fast= fast.next.next
	if slow==fast: return True

	return False

	#-----------------------hash---------------------------------
	#runtime complexity: O(n) n=len(nodes) space complexity: O(n)
	d= collections.defaultdict(int)
	while head:
	if d[head]: return True
	d[head]= True
	head = head.next
	return False