LeetCode---【链表的操作】

206反转链表【链表结构基础】

• 设定一个前结点和后结点。

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre=None
        cur=head
        while cur!=None:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre
1
2
3
4
5
6
7
8
9
10
11
12
13
14

21合并两个有序链表【递归】

我的答案【错误】

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        resol=ListNode()
        while list1!=None and list2!=None:
            if list1.val<=list2.val:
                resol.next=ListNode(list1.val)
            else:
                resol.next=ListNode(list2.val)
            list1=list1.next
            list2=list2.next

        while list1!=None:
            resol.next=ListNode(list1.val)
        while list2!=None:
            resol.next=ListNode(list2.val)
            
        return resol.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

自己修改【超出时间限制】

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        resol=ListNode(0)
        temp=resol
        while list1 and list2:
            if list1.val<=list2.val:
                resol.next=list1
                list1=list1.next################
            else:
                resol.next=list2
                list2=list2.next################
            resol=resol.next######################其实是不断增加结点的过程，所以记得更新
        while list1:
            resol.next=list1
        while list2:
            resol.next=list2
            
        return temp.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在官方那里学到的【然后自己复写,错误】

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        else:
            if list1.val<list2.val:
                list1.next=mergeTwoLists(self,list1.next,list2)###如果只改mergeTwoLists(self,list1.next,list2)也是可以编译通过的，运行成功，else这里的逻辑也可以修正一下
                return list1
            else:
                list2.next=mergeTwoLists(self,list2.next,list1)
                return list2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对照官方【自己修改】

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val<list2.val:
            list1.next=self.mergeTwoLists(list1.next,list2)########函数的调用
            return list1
        else:
            list2.next=self.mergeTwoLists(list2.next,list1)########函数的调用
            return list2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

160相交链表【未理解题目目的】

• 我看输入部分都已经给了要输出的结果了，就不明白这题目的是要做什么。

在b站up那里学到的【然后自己复写,错误】

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p=headA,q=headB
        while(p!=q):
            p ? p.next : headB
            q ? q.next : headA
        print("p.val")
1
2
3
4
5
6
7
8
9
10
11

【超出时间限制】

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p=headA
        q=headB
        while(p!=q):
            if p.next !=None:
                p=p.next
            else:
                p=headB
            if q.next!=None:
                q=q.next
            else:
                q=headA
        return p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对照官方【自己修改】

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p=headA ####p,q=headA,headB这样可以
        q=headB ####p=headA,q=headB会报错
        while(p!=q):
            p = p.next if p else headB
            q = q.next if q else headA
        return p
1
2
3
4
5
6
7
8
9
10
11
12

19删除链表的倒数第 N 个结点

看完官方解题思路【自己复写，错误】

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
       p=head
       for i in range(n+1):
           p=p.next
       q=head
       while p!=None:
           q=q.next
           p=p.next###########【这里不能少啊！】
       q.next=q.next.next
       return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

报错信息

• 查阅资料后发现：【self.head是指向第一个元素的，此时为None,所以没有next属性，自然就会报错。因此第一个结点需要特殊处理，我们一般通过增加头结点的方式来避免这种特殊处理。】

第一遍修改

• 发现当链表有n个元素时，无法删除倒数第n个元素。
• 【没有考虑到第一个结点的特殊性。】

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """

        p=ListNode(0, head)#################
        for i in range(n+1):
            p=p.next
        q=ListNode(0, head)#################
        while p!=None:
            q=q.next
            p=p.next
        q.next=q.next.next#########无法删除倒数第n个元素
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二遍修改

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """

        dummy=ListNode(0, head)
        p=dummy
        for i in range(n+1):
            p=p.next
        q=dummy
        while p!=None:
            q=q.next
            p=p.next
        q.next=q.next.next
        return dummy.next 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

148排序链表

我的答案【冒泡排序：最小的负数输出时变为0】

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy=ListNode(0,head)
        q=dummy
        while q.next!=None:
            p=dummy
            while p.next!=None:
                if p.val>p.next.val:
                    temp=p.val
                    p.val=p.next.val
                    p.next.val=temp
                p=p.next
            q=q.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

官方答案【归并排序】

class Solution(object):
    def sortList(self, head):
        def sortFunc(head, tail):
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(sortFunc(head, mid), sortFunc(mid, tail))
        ######合并两个升序链表，但是长度差最多为1    
        def merge(head1, head2):
            dummyHead = ListNode(0)
            temp, temp1, temp2 = dummyHead, head1, head2
            while temp1 and temp2:
                if temp1.val <= temp2.val:
                    temp.next = temp1
                    temp1 = temp1.next
                else:
                    temp.next = temp2
                    temp2 = temp2.next
                temp = temp.next
            if temp1:
                temp.next = temp1
            elif temp2:
                temp.next = temp2
            return dummyHead.next
        
        return sortFunc(head, None)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35