3个月用python刷完leetcode600题!-linked_list简单题

python基础

浏览数:886

2019-2-24

作者:石晓文 Python爱好者社区专栏作者

个人公众号:小小挖掘机

博客专栏:
wenwen

十五天的时间,刷完了所有的简单题,避免遗忘,所以开始简单题的二刷,第一遍刷题的时候过得速度比较快,因为我觉得基础不好的我,不要硬着头皮去想最优的方法,而是应该尽量去学一些算法思想,所以每道题只给自己5-10分钟的时间想,想不出来的就去找相关的答案,所以刷的比较快。二刷的时候按照leetcode官方给出的题目分类展开,同时,将解题思路记录于简书加深印象。
想要一起刷题的小伙伴,我们一起加油吧!
我的github连接:https://github.com/princewen/leetcode_python

21. Merge Two Sorted Lists

Merge Two Sorted Lists

很简单的链表拼接题,但是要注意两个地方
1、返回值要返回head.next
2、无需判断循环后哪个不为空,or返回第一个为真的值

# 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
        """
        head = cur = ListNode(0)
        while l1 and l2:
            if l1.val > l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1
                l1 = l1.next
            cur = cur.next
        cur.next = l1 or l2
        return head.next

83. Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

从链表中删除元素,一般需要两个指针来完成,分别记录要删除的链表元素和上一个元素。按照这个思路:

# 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:
            return head
        p = head
        q = head.next
        while q:
            if q.val == p.val:
                p.next = q.next
                q = q.next
            else:
                p = p.next
                q = q.next
        return head

两个指针比较容易理解,但是这里其实用一个指针就可以完成:

# 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
        """
        cur = head
        while cur:
            while cur.next and cur.val == cur.next.val:
                cur.next = cur.next.next
            cur = cur.next
        return head

141. Linked List Cycle

Linked List Cycle

判断链表中是否是有环,采用追赶法的思路,设置一个walker,每次走一步,设置一个runner,每次跑两步,当runner追上walkder时,说明链表中有环存在。

# 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
        """
        if not head:
            return False
        walker = head
        runner = head.next
        try:
            while walker!=runner:
                walker = walker.next
                runner = runner.next.next
            return True
        except:
            return False

160. Intersection of Two Linked Lists

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
        pa = headA
        pb = headB
        while pa is not pb:
            pa = headB if pa == None else pa.next
            pb = headA if pb == None else pb.next
        return pa

203. Remove Linked List Elements

Remove Linked List Elements

“有了第83题的思路,我们这里可以用一个指针来进行链表的遍历,但是这里需要注意的是,头节点也需要进行判断,如果头节点的值等于val的话,我们不能返回头节点,所以这里很巧妙的重新生成了一个无关的头节点。

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

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        cur = dummy
        while cur:
            while cur.next and cur.next.val == val:
                cur.next = cur.next.next
            cur=cur.next
        return dummy.next

206. Reverse Linked List

Reverse Linked List

链表转置,这里实在想不到一个指针的解法了,只能用两个指针,再加上head的帮忙,p指针记录的是每次的队头元素,q指针指向下一个要插入队头的元素。

# 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 None
        p = head
        q = head.next
        while q:
            head.next = q.next
            q.next = p
            p = q
            q = head.next
        return p

234. Palindrome Linked List

Palindrome Linked List

判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解:
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 isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        node = None
        while slow:
            nxt = slow.next
            slow.next = node
            node = slow
            slow = nxt

        while node and head:
            if node.val != head.val:
                return False
            node = node.next
            head = head.next
        return True

237. Delete Node in a Linked List

Delete Node in a Linked List

这道题关键是理解题意,不给你整个链表,只给你一个节点,如何把这个节点删除,其实我们没必要真的把这个节点删除,而是把这个节点对应的val值删除即可,所以我们可以偷天换日,把下一个节点的值赋给这个节点,再把下一个节点删除。

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

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