二刷 leetcode （9）

旧城等待， 2022-05-20 04:42 197阅读 0赞

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

代码：

# 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
            """
            ####  the first method
            newHead = ListNode(0)
            pre = newHead
            while l1 and l2:
                if l1.val < l2.val:
                    newHead.next = l1
                    l1 = l1.next
                else:
                    newHead.next = l2
                    l2 = l2.next
                newHead = newHead.next
            if l1:
                newHead.next = l1
                list.append(pre.next.val)      
            elif l2:
                newHead.next = l2
                list.append(pre.next.val)
            return pre.next
            
            #### the second method
            if l1 == None:
                return l2
            if l2 == None:
                return l1
            dummy = ListNode(0)
            tmp = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    tmp.next = l1
                    l1 = l1.next
                    tmp = tmp.next
                else:
                    tmp.next = l2
                    l2 = l2.next
                    tmp = tmp.next
            if l2 == None:
                tmp.next = l1
            else:
                tmp.next = l2
            return dummy.next

141. 环形链表

给定一个链表，判断链表中是否有环。

代码;

# 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
            """
            #### the first method 
            
            # slow = fast = head
            # if head == None or head.next == None:
            #     return False
            # while fast and fast.next:
            #     slow = slow.next
            #     fast = fast.next.next
            #     if fast == slow:
            #         return True
            # return False
            
            #### the second method
            
            slow = fast = head
            while fast:
                slow, fast = slow.next, fast.next
                if not fast:
                    return False
                fast = fast.next
                if fast == slow:
                    return True
            return False

234. 回文链表

给定一个链表，判断链表中是否有环。

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
    输出: false

示例 2:

输入: 1->2->2->1
    输出: true

代码:

# 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
            """
            #####  the first method
    #         if head == None or head.next == None:
    #             return True
    #         values = []
    #         p = head
    #         while p.next:
    #             values.append(p.val)
    #             p = p.next
    #         values.append(p.val)
            
    #         return values[:] == values[::-1]
    
            ##### the second method
            if head is None or head.next is None:
                return True
            mid = ListNode(0)
            mid.next = head
            fast = mid
            while fast and fast.next:
                mid = mid.next
                fast = fast.next.next
            
            pre = mid 
            cur = mid.next
            while cur:
                temp  = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            
            start = head
            end = pre
            if start.val != end.val:
                return False
            while start != mid.next:
                if start.val != end.val:
                    return False
                start = start.next
                end = end.next
            return True

给定一个链表，判断链表中是否有环。