链表在python中是可以自定义的,属性包括val和next。一般表示链表都是用头节点表示,得到下一个节点用next,都是地址,想要得到值用val。
简单来说,就是求两个链表交点节点的 指针。 这里要注意,交点不是数值相等,而是指针相等。
- # 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
- """
- # 用顺序遍历的方法
- p, q = headA, headB
- # 先得到两个链表的长度
- lenA = 0
- lenB = 0
- while p != None:
- p = p.next
- lenA += 1
- while q != None:
- q = q.next
- lenB += 1
- # 尾部对齐
- # 再次将pq对准链表头节点
- p, q = headA, headB
- if lenA < lenB:
- temp = lenB - lenA
- while temp != 0:
- q = q.next
- temp -= 1
- else:
- temp = lenA - lenB
- while temp != 0:
- p = p.next
- temp -= 1
- # 同时向后遍历
- len_min = min(lenA, lenB)
- for i in range(len_min):
- if p == q:
- return p
- else:
- p = p.next
- q = q.next
-
- return None
看了解析,自己用倒序法做做试试。
- # 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
- """
- # 用倒序遍历的方法
- # 用栈,先将地址顺序存进去,然后倒着遍历
- p, q = headA, headB
- # 先得到两个链表的长度
- lenA = 0
- lenB = 0
- listA = []
- listB = []
- while p != None:
- listA.append(p)
- p = p.next
- lenA += 1
- while q != None:
- listB.append(q)
- q = q.next
- lenB += 1
-
- len_min = min(lenA, lenB)
- result = None
- for i in range(len_min):
- if listA[lenA-1-i] == listB[lenB-1-i]:
- result = listA[lenA-1-i]
- else:
- return result
- return result
-
-
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
心得:若节点被引用,如p=head,这时改变head会使p也改变。所以需要提前存储节点。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def reverseList(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- # 值反转还是地址反转
- # 地址反转,因为读取链表的值需要一直遍历得到
- length = 0
- p = head
- q = head
- list_ = []
- while p != None:
- list_.append(p)
- length += 1
- q = p
- p = p.next
- p = head
- # 需要倒序遍历储存了节点地址的列表
- for i in reversed(range(length)):
- if i == 0:
- list_[i].next = None
- else:
- list_[i].next = list_[i-1]
-
- return q
-
一开始就想的这个方法,可惜不知道怎么实现。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def reverseList(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- pre = None
- cur = head
-
- while cur != None:
- nex = cur.next
- cur.next = pre
- pre = cur
- cur = nex
-
- return pre
第一时间想的就是把节点的值都存储到数组中,然后直接判断数组是否回文。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def isPalindrome(self, head):
- """
- :type head: ListNode
- :rtype: bool
- """
- p = head
- length = 0
- values = []
- while p != None:
- values.append(p.val)
- length += 1
- p = p.next
-
- for i in range(length/2):
- if values[i] == values[length-i-1]:
- continue
- else:
- return False
-
- return True
用快慢指针的方法能够节省很多空间
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def isPalindrome(self, head):
- """
- :type head: ListNode
- :rtype: bool
- """
- p = head
- # 用快慢指针
- fast = head
- slow = head
- # 1.找到前半部分尾节点
- while fast != None:
- if fast.next == None:
- break
- elif fast.next.next == None:
- break
- slow = slow.next
- fast = fast.next.next
- # 慢指针为前半部分的尾节点
- # 2.反转后半部分链表
- pre = None
- cur = slow
- while cur != None:
- nex = cur.next
- cur.next = pre
- pre = cur
- cur = nex
- # 3.判断是否回文
- while p != None:
- val1 = p.val
- val2 = pre.val
- if val1 != val2:
- return False
- p = p.next
- pre = pre.next
- # 4.恢复链表,和第二步一样操作
- # 5.返回结果
- return True
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
心得:想到哈希表,虽然ac了,但时间跟空间都不行。
- # 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
- """
- # 第一时间想到用字典,键值名是节点地址,键值是索引
- # 不需要返回环在第几个,可以用哈希表
- hash_table = set()
- p = head
- while p != None:
- if p in hash_table:
- return True
- else:
- hash_table.add(p)
- p = p.next
-
- return False
思考:环形链表有尾节点吗,有地址是None的情况吗。
答:没有尾节点,地址没有None的情况。
- # 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 head == None:
- return False
- elif head.next == None:
- return False
- pre = None
- slow = head
- fast = head.next
- while slow != None:
- if fast == pre or fast == slow:
- return True
- if fast.next==None or fast.next.next==None:
- return False
- pre = slow
- slow = slow.next
- fast = fast.next.next
-
- return False
因为环形链表没有None,所以暴力解法。
- # 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
- """
- # 因为环形链表没有None
- # 且数目最大是10**4
- p = head
- length = 0
- while 1:
- if p == None:
- return False
- else:
- length += 1
- p = p.next
- if length > 10000:
- return True
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
心得:还是先用哈希表做。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.next = None
-
- class Solution(object):
- def detectCycle(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- # 用哈希表记录地址
- hash_table = set()
- p = head
- while p != None:
- if p not in hash_table:
- hash_table.add(p)
- else:
- return p
- p = p.next
看了题解,用快慢指针做,太复杂了,纯考数学啊。
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
可以先创建一个val为-1的单链表,然后在其基础上拓展。思路还是挺简单的。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def mergeTwoLists(self, list1, list2):
- """
- :type list1: Optional[ListNode]
- :type list2: Optional[ListNode]
- :rtype: Optional[ListNode]
- """
- # 比较val的大小,然后决定next的地址
- # 头指针
- neww = ListNode(-1)
- # 移动指针
- new = neww
- while 1:
- if list1 == None:
- while list2 != None:
- new.next = list2
- new = new.next
- list2 = list2.next
- break
- elif list2 == None:
- while list1 != None:
- new.next = list1
- new = new.next
- list1 = list1.next
- break
-
- if list1.val <= list2.val:
- new.next = list1
- list1 = list1.next
- else:
- new.next = list2
- list2 = list2.next
-
- new = new.next
-
- return neww.next
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
心得:逻辑挺简单的就是进位注意不要遗忘。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def addTwoNumbers(self, l1, l2):
- """
- :type l1: ListNode
- :type l2: ListNode
- :rtype: ListNode
- """
- neww = ListNode(-1)
- new = neww
- up = 0
- while l1 != None or l2 != None:
- if l1 != None and l2 != None:
- if l1.val + l2.val + up < 10:
- temp = ListNode(l1.val + l2.val + up)
- up = 0
- else:
- temp = ListNode((l1.val + l2.val + up)%10)
- up = 1
- l1 = l1.next
- l2 = l2.next
- elif l1 == None:
- if l2.val + up < 10:
- temp = ListNode(l2.val + up)
- up = 0
- else:
- temp = ListNode(0)
- up = 1
- l2 = l2.next
- elif l2 == None:
- if l1.val + up < 10:
- temp = ListNode(l1.val + up)
- up = 0
- else:
- temp = ListNode(0)
- up = 1
- l1 = l1.next
-
- new.next = temp
- new = new.next
-
- if up == 1:
- temp = ListNode(1)
- new.next = temp
- new = new.next
-
- return neww.next
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
示例 1:
先试试第三种方法
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def removeNthFromEnd(self, head, n):
- """
- :type head: ListNode
- :type n: int
- :rtype: ListNode
- """
- # 几种方法
- # 1、先翻转,再删除第n个节点,再翻转
- # 2、计算长度,然后再遍历一遍,删掉节点
- # 3、计算长度并将地址存入数组,直接索引删除节点
- p = head
- index = []
- length = 0
- while p != None:
- length += 1
- index.append(p)
- p = p.next
-
- target = length - n
- if target == 0:
- return head.next
- if n == 1:
- index[target-1].next = None
- else:
- index[target-1].next = index[target+1]
-
- return head
再试试第二种
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def removeNthFromEnd(self, head, n):
- """
- :type head: ListNode
- :type n: int
- :rtype: ListNode
- """
- # 几种方法
- # 1、先翻转,再删除第n个节点,再翻转
- # 2、计算长度,然后再遍历一遍,删掉节点
- # 3、计算长度并将地址存入数组,直接索引删除节点
- p = head
- length = 0
- while p != None:
- length += 1
- p = p.next
-
- target = length - n
- num = 0
- if target == 0:
- return head.next
-
- p = head
- while p != None:
- num += 1
- if num == target:
- p.next = p.next.next
- break
- p = p.next
-
- return head
第一种时间复杂度太高,就不试了。
看了解析,这种倒数第几个的方式应该要想到用栈来做,弹出的第n个节点就为需要删除的节点了。
哑节点的设置
dummy = ListNode(0, head)
心得:看到一个双指针的方法,用两个指针,中间相差n,当一个指针到达尾部时,另一个就在目标位置,删除即可,没想到,可惜。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def removeNthFromEnd(self, head, n):
- """
- :type head: ListNode
- :type n: int
- :rtype: ListNode
- """
- count = 0
- dummy_note = ListNode(0,head)
- fast = dummy_note
- slow = dummy_note
- while fast != None:
- if count > n:
- slow = slow.next
- count += 1
- fast = fast.next
-
- slow.next = slow.next.next
-
- return dummy_note.next
时间太长了吧。
心得:节点的地址永远不变,但表示地址的变量随时可以改变。要注意,要赋值的地址在上一两行不能改变,不然就混乱了,要合理安排赋值的顺序。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def swapPairs(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- # 1、把地址全存下来改
- # 2、遍历一遍并修改
- # 局部翻转链表
- # 两两交换需要三步
- if head == None:
- return head
- elif head.next == None:
- return head
-
- pre = ListNode(0,head)
- result = pre
- cur = head
- while cur:
- if cur.next == None:
- break
- back = cur.next
- cur.next = back.next
- back.next = cur
- pre.next = back
-
- pre = cur
- cur = cur.next
-
- return result.next
- """
- # Definition for a Node.
- class Node:
- def __init__(self, x, next=None, random=None):
- self.val = int(x)
- self.next = next
- self.random = random
- """
-
- class Solution(object):
- def copyRandomList(self, head):
- """
- :type head: Node
- :rtype: Node
- """
- if head == None:
- return None
- p = head
- q = head.next
- result = Node(p.val)
- cur = result
- i = result
- # 先生成单链表
- # 用双循环,当外层指针的random等于内层指针地址时,新链表的random也等于这个位置的地址
- while q:
- back = Node(q.val)
- cur.val = p.val
- cur.next = back
-
- cur = cur.next
- p = p.next
- q = q.next
-
- p = head
- k = result
- while p:
- i = result
- j = head
- while i:
- if p.random == None:
- k.random = None
- break
-
- if p.random == j:
- k.random = i
-
- i = i.next
- j = j.next
-
- p = p.next
- k = k.next
-
- return result
在题解评论中看到一个很巧妙的方法,试了一下确实很通俗易懂。
- """
- # Definition for a Node.
- class Node:
- def __init__(self, x, next=None, random=None):
- self.val = int(x)
- self.next = next
- self.random = random
- """
-
- class Solution(object):
- def copyRandomList(self, head):
- """
- :type head: Node
- :rtype: Node
- """
- if head == None:
- return None
-
- # 将新老节点地址储存在一起,遍历得到对应的next和random
- store = {}
- p = head
- while p:
- store[p] = Node(p.val)
- p = p.next
-
- p = head
- while p:
- if p.next == None:
- store[p].next = None
- else:
- store[p].next = store[p.next]
- if p.random == None:
- store[p].random = None
- else:
- store[p].random = store[p.random]
- p = p.next
-
- return store[head]
给你链表的头结点 head
,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3] 输出:[1,2,3,4]
心得:想法是地址随着val排序,结果超时了。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def sortList(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- if head == None:
- return None
- # 把地址和对应的val存储起来
- # 先排序val,然后相应的地址也会改变
- p = head
- addrees = []
- length = 0
- while p:
- length += 1
- addrees.append(p)
- p = p.next
-
- for i in range(length):
- j = 0
- while j < length - i - 1:
- if addrees[j].val > addrees[j+1].val:
- temp_addrees = addrees[j]
- addrees[j] = addrees[j+1]
- addrees[j+1] = temp_addrees
- j += 1
-
- dummy = ListNode(0)
- head = addrees[0]
- dummy.next = head
- for i in range(1,length):
- head.next = addrees[i]
- head = head.next
- head.next = None
-
- return dummy.next
链表适合归并排序,冒泡、插入、归并都必须掌握。
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
- class Solution(object):
- def sortList(self, head):
- """
- :type head: ListNode
- :rtype: ListNode
- """
- 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))
-
- 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)