LinkedList

1 Reverse Linked List

这道题iteration和recursion都要会写啊。

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return

        tail = None
        while head:
            new_head = head.next
            head.next = tail
            tail = head
            head = new_head

        return tail

reversion

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        self.root = None
        self.helper(head, head.next)
        return self.root


    def helper(self, pre, cur):
        if not cur:
            self.root = pre
            return
        next = cur.next
        cur.next = pre
        self.helper(cur, next)

2 Add Two Numbers

重新build一个 dummy node 然后把两个接起来。结尾要处理l1, l2长度不一样的情况，还有剩余的carry=1的情况。

# 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
        """

        head = tmp = ListNode(-1)
        carry = 0
        while l1 and l2:
            val = carry + l1.val + l2.val
            carry = val//10
            tmp.next = ListNode(val%10)
            tmp = tmp.next
            l1, l2 = l1.next, l2.next

        rest = l1 or l2
        while rest:
            val = carry + rest.val
            carry = val//10
            tmp.next = ListNode(val%10)
            tmp = tmp.next
            rest = rest.next

        if carry:
            tmp.next = ListNode(1)


        return head.next

3 Remove Nth Node From End of List

大致思想就是用一个fast 和slow。

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

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        fast = dummy
        slow = dummy

        for i in range(n):
            fast = fast.next

        while fast.next:
            slow = slow.next
            fast = fast.next


        slow.next = slow.next.next
        return dummy.next

4 Intersection of Two Linked Lists

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

5 Flatten Binary Tree to Linked List

# 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.
        """

        if not root:
            return

        og_right = root.right
        if root.left:
            self.flatten(root.left)
            tail = root.left
            while tail.right:
                tail = tail.right
            tail.right = og_right
            root.right = root.left
            root.left = None
        self.flatten(og_right)

6 Linked List Cycle

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False