链表

今天开始抽空刷一些leetcode里数据结构的题，在这里记录下来。按难易程度开始刷吧。

第一次更新：2018.10.15

237、删除链表中的节点
开始看题的时候有点懵，没太懂题目意思，删除链表中值为某个值的节点，但题目没有给定链表。后来想了一会，直接用该链表的下一个节点覆盖掉这个节点就可以了。

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        if node:        
            node.val = node.next.val
            node.next = node.next.next

206、反转链表
先用迭代实现

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        a, b, c = None, head, head.next
        while c:
            b.next = a
            a, b, c = b, c, c.next
        b.next = a
        return b

再用递归

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

21、合并两个有序链表

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        head = ListNode(-1)
        temp = head
        while l1 and l2:
            if l1.val <= l2.val:
                temp.next = l1
                l1 = l1.next
                temp = temp.next
            else:
                temp.next = l2
                l2 = l2.next
                temp = temp.next
        if l1:
            temp.next = l1
        if l2:
            temp.next = l2
        return head.next

83、删除排序链表中的重复元素

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

203、移除链表元素

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """ 
        new_head = ListNode(val-1)
        temp = new_head
        cur = head
        while cur:
            if cur.val != val:
                temp.next = cur
                temp = temp.next
            cur = cur.next
        temp.next = None
        return new_head.next

234、回文链表
第一次做的时候把值存在了列表里，然后判断列表是不是回文列表。可以用双指针找到中间的节点，还要用到之前的反转链表，代码比较长，也是调试了几次才AC。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        def reverseList(head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head:
                return None
            a, b, c = None, head, head.next
            while c:
                b.next = a
                a, b, c = b, c, c.next
            b.next = a
            return b

        if not head or not head.next:
            return True
        slow = head
        fast = head
        while fast.next:
            if not fast.next.next:
                break
            else:
                fast = fast.next.next
                slow = slow.next
        new_listnode = reverseList(slow.next)
        p = new_listnode
        q = head
        while p:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return True
        

第二次更新：2018.10.16

141、环形链表
使用快指针和慢指针就可以了

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

160、相交链表
剑指offer里面也有这题

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p1 = headA
        p2 = headB
        while p1 != p2:
            p1 = p1.next if p1.next else headB
            p2 = p2.next if p2.next else headA
        return p1

109、有序链表转换二叉搜索树
今天在剑指offer里刷了一道二叉搜索树转双向链表的，这道题反过来将链表转二叉搜索树。有序链表的顺序就是二叉搜索树的中序遍历的顺序。
只要找到中间的节点，然后递归就可以了。但是链表找中间节点有点麻烦，可以用笨办法先转为列表再找中间节点，然后重新转化为节点。但用双指针也可以找到中间节点，不过在递归过程中不断找中间节点有点困难，没有写出来。还是参考了别人的代码

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

        def convert(head, tail):
            if head == tail:
                return None
            if head.next == tail:
                return TreeNode(head.val)
            fast = head
            mid = head
            while fast != tail and fast.next != tail:
                fast = fast.next.next
                mid = mid.next
            root = TreeNode(mid.val)
            root.left = convert(head, mid)
            root.right = convert(mid.next, tail)
            return root

        return convert(head, None)

24、两两交换链表中的节点
直接用递归

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head
        a, b = head, head.next
        temp = self.swapPairs(b.next)
        b.next = a
        a.next = temp
        return b

114、二叉树转为链表
要求原地修改二叉树，所以不能先序遍历再连接。

class Solution(object):
    def flatten(self, root):
        if not root:
            return None
        if root.left:
            self.flatten(root.left)
        if root.right:
            self.flatten(root.right)
        temp = root.right
        root.right = root.left
        root.left = None
        while root.right:
            root = root.right
        root.right = temp

148、排序链表
题目要求了时间复杂度：O(n log n)。好像快排，归并排序，堆排序都是O(n log n)级别的，但我还没看，先跳过

382、链表随机节点
获得长度后用random模块随机一个数字代表第几个节点

class Solution(object):

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        import random
        self.head = head

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        if not self.head:
            return None
        length = 0
        cur = self.head
        while cur:
            length += 1
            cur = cur.next
        index = random.randint(0, length-1)
        cur = self.head
        for i in range(length):
            if i == index:
                return cur.val
            else:
                cur = cur.next
                i += 1

147、对链表进行插入排序
剑指offer刷完我就去看排序！先跳过

328、奇偶链表
用了三个指针。

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        a, b, c = head, head.next, head.next.next
        new_head = b
        i = 0
        while c:
            i += 1 
            a.next = c
            a, b, c = b, c, c.next
        if i%2 == 0:
            a.next = new_head
        else:
            b.next = new_head
            a.next = None
        return head

第三次更新：2018.10.17
明天要开组会，准备了一晚上组会的东西= =，抓紧时间写两道题

143、重排链表
写了很久，想法是后半段链表先翻转，然后前半段和后半段交叉连接就可以了。

class Solution(object):
    def reorderList(self, head):

        def reverse(head):
            if not head:
                return None
            a, b, c = None, head, head.next
            while c:
                b.next = a
                a, b, c = b, c, c.next
            b.next = a
            return b

        if  head and head.next:
            fast = head
            slow = head
            while fast.next:
                if fast.next.next:
                    fast = fast.next.next
                    slow = slow.next
                else:
                    break
            new_head = reverse(slow.next)
            a = head
            b = new_head
            final_head = ListNode(0)
            temp = final_head
            i = 0
            while b:
                if i%2==0:
                    temp.next = a
                    temp = temp.next
                    a = a.next
                if i%2 == 1:
                    temp.next = b
                    temp = temp.next
                    b = b.next
                i += 1
            temp.next = a
            if temp.next:
                temp.next.next = None
            head = temp.next

2、两数相加
最简单的可以直接将数值取出来再相加。当然有更好的解法，参考了别人的，用memory记录进位

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        mem = 0
        new_head = ListNode(0)
        cur = new_head
        while l1 or l2:
            a = l1.val if l1 else 0
            b = l2.val if l2 else 0
            c = a + b
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
            cur.next = ListNode((c+mem)%10)
            cur = cur.next
            mem = (c+mem) // 10
        if mem != 0:
            cur.next = ListNode(mem)
        return new_head.next

445、两数相加Ⅱ
这题跟上一题类似，不过上一题最高位处于链表的尾节点，这题最高位处于头节点。简单一点的可以将两个链表反转后再复制上一题的代码，但应该有更好的答案，但我没想出来。网上搜了一下其实就是把值都取出来存在栈里==。看来是我想复杂了

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        stack1 = []
        stack2 = []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        answer = None
        carry = 0
        while stack1 and stack2:
            add = stack1.pop() + stack2.pop() + carry
            carry = 1 if add >= 10 else 0
            temp = answer
            answer = ListNode(add % 10)
            answer.next = temp
        l = stack1 if stack1 else stack2
        while l:
            add = l.pop() + carry
            carry = 1 if add >= 10 else 0
            temp = answer
            answer = ListNode(add % 10)
            answer.next = temp
        if carry:
            temp = answer
            answer = ListNode(1)
            answer.next = temp
        return answer

86、分隔链表
用了个比较笨的办法，用一个新链表存储小于目标值的节点，另一个新链表存储其它节点，最后再合并

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        smallhead = ListNode(-1)
        bighead = ListNode(-1)
        a , b= smallhead, bighead
        cur = head
        while cur:
            if cur.val < x:
                a.next = cur
                a = a.next
                cur = cur.next
            else :
                b.next = cur
                b = b.next
                cur = cur.next
        a.next = None
        b.next = None
        cur = smallhead
        while cur.next:
            cur = cur.next
        cur.next = bighead.next
        return smallhead.next

92、反转链表Ⅱ
跟反转链表第一题差不多，注意一下反转的界限就可以了。实际写的时候出了很多问题，最终还是没写出来。。参考别人代码，实际思路是一样的

class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if head == None or head.next == None or m >= n or m < 0 or n < 0:
            return head

        h = ListNode(-1)
        h.next = head
        pre = h
        cur = head
        i = 1
        while i < m and cur != None:
            pre = cur
            cur = cur.next
            i += 1

        t1 = pre
        t2 = cur

        while i <= n and cur != None:
            lat = cur.next
            cur.next = pre
            pre = cur 
            cur = lat
            i += 1

        t1.next = pre
        t2.next = cur
        return h.next

2018.10.20

82、删除链表中的重复元素Ⅱ

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def deleteDuplicates(self, head):
        if not head:
            return None
        new_head = ListNode(head.val - 1)
        temp = new_head
        a, b, c = temp, head, head.next
        while b:
            if not c:
                if b.val != a.val:
                    temp.next = b
                    break
                else:
                    temp.next = None
                    break
            elif a.val != b.val != c.val:
                temp.next = b
                temp = b
                a, b, c = b, c, c.next
            else:
                a, b, c = b, c, c.next
        b.next = None
        return new_head.next

61、旋转链表
调试了很久才AC。

class Solution(object):
    def rotateRight(self, head, k):
        if not head:
            return None
        if k == 0:
            return head
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next
        if length == 1 or k%length==0:
            return head
        pos = length - k % length + 1
        cur = head
        i = 1
        while i < pos-1:
            cur = cur.next
            i += 1
        temp = cur
        new_head = cur.next
        cur = cur.next
        while cur.next:
            cur = cur.next
        temp.next = None
        cur.next = head
        return new_head

19、删除链表的倒数第N个节点
遍历两遍链表的话很容易，但一遍的话没想到该怎么做。参考别人的答案：https://blog.csdn.net/dongrongyu/article/details/78346583

想法是这样的：维护两个指针，pre和end。一开始初始化时使得pre指针指向链表头节点，end指针指向pre+n的节点位置。然后同时往后移动pre和end指针位置，使得end指针指向最后一个节点，那么pre指针指向的则是end-n的节点位置（即倒数第n个元素的前一个节点），则将其删除。

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return None
        fast = head
        for i in range(n):
            fast = fast.next
        if not fast:
            return head.next
        slow = head
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

142、环形链表Ⅱ
剑指offer里刷过了

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        fast = head
        slow = head
        while fast.next:
            if not fast.next.next:
                return None
            else:
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    if fast==head:
                        return head
                    slow = head
                    while True:
                        fast = fast.next
                        slow = slow.next
                        if fast == slow:
                            return fast
        return None