LeetCode #83 #206 #21 #876 2018-

Part 1 – Basic Skills in Linked List

以下要介绍的链表基础技术非常重要，虽然可能不会直接出如此简单的题目，但几乎所有的链表题目都要使用这些基础技术做为Subroutine，娴熟的掌握链表基础技术可以让你将复杂题目拆解成由基础技术组成的Subroutine，让复杂题目也可以迎刃而解。

下面以4段代码来分别讲解这些基础技术：

83. Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/

由于增删一个结点很类似，所以选择了一道删除的题目来代表此类操作。增删一个结点的关键是使用“差一法”，即获得要增加或者删除位置结点的前一个结点pre，然后使用pre.next = cur.next来将cur结点删除。
代码如下：

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

class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        pre = head
        cur = head.next
        while cur:
            if pre.val == cur.val:
                pre.next = cur.next
            else:
                pre = pre.next
            cur = cur.next
        return head

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/

反转链表也是链表题目中很常见的操作，所以我们一定要熟悉。在这里介绍两种反转链表的方法，分别用递归和迭代完成。
递归代码如下：

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

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

迭代代码如下：

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

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/

合并两个链表也是很常见的链表操作。这里用到了Dummy Node技术，而且这种以一个链表为模板，将另一个链表插入其中的思想也值得借鉴。
代码如下：

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = pre = ListNode(0)
        dummy.next = l1
        pre = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                l1 = l1.next
            else:
                next = l2.next
                l2.next = pre.next
                pre.next = l2
                l2 = next
            pre = pre.next
        if l2:
            pre.next = l2
        return dummy.next

876. Middle of the Linked List

https://leetcode.com/problems/middle-of-the-linked-list/description/

找链表中点的操作往往在要将链表一分为二的题目当中，例如使用Merge Sort来解Sort List这道题时就会使用到。同时这里还使用到了Two Pointers技术，也叫walker & runner技术，后面会具体说明。
代码如下：

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

class Solution:
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        walker = head
        runner = head
        while runner and runner.next:
            walker = walker.next
            runner = runner.next.next
        return walker