LeetCode #86 #2 #445 2018-08-08

86. Partition List

https://leetcode.com/problems/partition-list/description/

这道题要求值小于x的结点必须出现在值大于等于x的结点左面。所以我们构造2个链表less和more来分别存储这两种结点，最后组合一下即可。注意，最后需要将preG.next置为None，不然会出现错误。
代码如下：

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

class Solution:
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummyG = preG = ListNode(0)
        dummyL = preL = ListNode(0)
        while head:
            next = head.next
            head.next = None
            if head.val < x:
                preL.next = head
                preL = preL.next
            else:
                preG.next = head
                preG = preG.next
            head = next
        preL.next = dummyG.next
        preG.next = None
        return dummyL.next

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/description/

这道题由于要构造一个新的链表来表示求和的结果，所以我们依然使用Dummy Node技术。题目比较简单，使用一个carry来保存进位即可。注意，最后如果carry不为0的话，说明还要新建一个结点来保存一个最高位。
代码如下：

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

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        dummy = pre = ListNode(0)
        carry = 0
        while l1 and l2:
            digit = l1.val + l2.val + carry
            carry = digit // 10
            digit = digit % 10
            cur = ListNode(digit)
            pre.next = cur
            pre = pre.next
            cur.next = None
            l1 = l1.next
            l2 = l2.next
        while l1:
            digit = l1.val + carry
            carry = digit // 10
            digit = digit % 10
            cur = ListNode(digit)
            pre.next = cur
            pre = pre.next
            cur.next = None
            l1 = l1.next
        while l2:
            digit = l2.val + carry
            carry = digit // 10
            digit = digit % 10
            cur = ListNode(digit)
            pre.next = cur
            pre = pre.next
            cur.next = None
            l2 = l2.next
        if carry:
            cur = ListNode(carry)
            pre.next = cur
            cur.next = None
        return dummy.next   

445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/

这里用了一个投机取巧的做法，先把两个数字分别算出来然后求和，根据求出的合来建立结果链表。
代码如下：

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

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        num1, num2 = 0, 0
        while l1:
            num1 = num1 * 10 + l1.val
            l1 = l1.next
        while l2:
            num2 = num2 * 10 + l2.val
            l2 = l2.next
        num = num1 + num2
        dummy = pre = ListNode(0)
        if num == 0:
            return dummy
        while num:
            digit = num % 10
            num = num // 10
            cur = ListNode(digit)
            cur.next = pre.next
            pre.next = cur
        return dummy.next