链表
题目:
- 链表删除某一个节点
- 删除倒数第N个节点
- 链表逆序
- 回文链表
- 判断链表是否有环路
- 找出环路链表的入口
- 链表排序
- 相交链表
- 两个连表生成相加链表
链表的数据格式就是如下:
需要注意的是:链表尾部的next为None
。所以判断链表结束时,这是遍历一个链表最常用的结束方式
。使用的代码:
while p != None:
p = p.next
其实是当p已经指向了next区域,这时next为空,所以能够退出
当使用p.next != None
时,这时p指向的最有一个节点,而不是节点的next。
while p.next != None:
p = p.next
链表删除某一个节点:
删除节点两种方式:
-
当前节点指向下下个节点
-
将下一个节点赋值给当前节点,然后删除下一个节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
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.val,node.val
node.next = node.next.next
删除倒数第N个节点
有两种方式:
- 算出倒数N的正数num,然后移动到该节点前一个,删除节点
- 设置双指针,指针的间距是倒数N。当快指针到链尾时,慢指针当好到待删除的前一个。
- 删除节点需要考虑节点为头结点的情况。这时指针指向头结点,不易删除。解决办法是给头结点增加一个前行节点。将指针指向该前行节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 设置头结点
re = ListNode(-1)
re.next = head
slow = re
fast = slow
while n + 1> 0:
fast = fast.next
n -= 1
while fast != None:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return re.next
链表逆序
使用双指针可以将链表逆序。
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
temp = cur.next # 先把原来cur.next位置存起来
cur.next = pre
pre = cur
cur = temp
return pre
需要注意结束条件。当cur == None
时,pre刚好在链尾的位置。返回pre就是返回了新的链表
回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
回文最常用的判断方式是:
- 逆序,然后比较逆序之后和逆序之前是否相同。如果相同就是回文,不同就不是回文
- 将前一半保存,逆序或者入栈,和后一半比较。如果都相同则是回文。
链表回文有多种方式:
- 将链表中所有数据保存到列表中,使用列表的逆序来判断
- 利用快慢指针,前一半链表的值入栈,然后出栈和后一半比较判断
- 利用快慢指针,逆序前一半链表,和后一半比较
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next:
return True
slow = head
fast = head
mystack = []
while fast and fast.next:
mystack.append(slow.val)
fast = fast.next.next
slow = slow.next
# 奇数状态,需要跨过中间的元素
if fast:
slow = slow.next
while slow and slow.val == mystack.pop():
slow = slow.next
判断链表是否有环路
判断链表是否有环路有两个解决方法,
第一:快慢指针,如果存在环路,快指针一定会追上慢指针
第二:字典。将遍历过的节点存入到字典中,每次遍历时在字典中查找,如果存在则表明有环路。
class Node():
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(100)
node2 = Node(200)
node3 = Node(300)
node4 = Node(300)
node5 = Node(200)
node6 = Node(100)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node1
def cycle_link(head):
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
res = cycle_link(node1)
print(res)
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head:
return False
Hash = {}
temp = head
while temp != None:
if Hash.get(temp):
return True
else:
Hash[temp] = True
temp = temp.next
return False
找出环路链表的入口
通过计算可以知道,快指针走的距离是慢指针距离的两倍,同时快指针比慢指针多走了一个圆的距离。所以在快慢指针相遇的地方,两个指针以相同的数据在走下去,相遇的地方就是环的入口
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
first = head
second = head
while first and first.next:
first = first.next.next
second = second.next
if first == second:
first = head
while True:
if first == second:
return first
first = first.next
second = second.next
return None
链表排序
使用链表这样数据结构实现排序,归并排序的实现如下:
先分开,后合并
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
slow = head
fast = head
# 用快慢指针分成两部分
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 找到左右部分, 把左部分最后置空
mid = slow.next
slow.next = None
# 递归下去
left = self.sortList(head)
right = self.sortList(mid)
# 合并
return self.merge(left, right)
def merge(self, left, right):
dummy = ListNode(0)
p = dummy
l = left
r = right
while l and r:
if l.val < r.val:
p.next = l
l = l.next
p = p.next
else:
p.next = r
r = r.next
p = p.next
if l:
p.next = l
if r:
p.next = r
return dummy.next
相交链表
编写一个程序,找到两个单链表相交的起始节点。
在节点 c1 开始相交。
原理:两个链表是否有相交的地方,可以通过如下方法测试出来:
走完A之后,从B起始点开始走,同样,走完B之后,从A开始走,这样如果有相交的位置,那么A和B到相交的位置就刚好一致。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not(headA and headB):
return None
nodea = headA
nodeb = headB
while nodea != nodeb:
if nodea is None:
nodea = headB
else:
nodea = nodea.next
if nodeb is None:
nodeb = headA
else:
nodeb = nodeb.next
return nodea
两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
输入:head = [1,2,3,4]
输出:[2,1,4,3]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
pre_head = ListNode(-1)
pre_head.next = head
pre_h = pre_head
p = head
while p and p.next:
next_p = p.next
p.next = next_p.next
pre_h.next = next_p
next_p.next = p
pre_h = p
p = p.next
return pre_head.next
两个连表生成相加链表
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
class Solution:
def addInList(self , head1 , head2 ):
def reverse_fun(head):
pre = None
p = head
while p:
temp = p.next
p.next = pre
pre = p
p = temp
return pre
re_head1 = reverse_fun(head1)
re_head2 = reverse_fun(head2)
d = ListNode(0)
p = d
c = 0
while re_head1 or re_head2 or c:
if re_head1:
c += re_head1.val
re_head1 = re_head1.next
if re_head2:
c += re_head2.val
re_head2 = re_head2.next
p.next = ListNode(c % 10)
p = p.next
c = c // 10
return reverse_fun(d.next)
链表解题总结
链表是我喜欢的数据结构,因为链表没有太多复杂操作。通常是遍历链表一直到尾节点,然后一边遍历一边配合指针操作。在链表中有几个小技巧可以好好总结一下:
- 使用快慢指针可以找到链表的中间位置。
一个指针是快指针,每次走两步,一个指针是慢指针,每次走一步。当快指针到末尾时,慢指针刚好在链表的中间位置。使用场景:回文链表,归并排序
while first and first.next:
first = first.next.next
second = second.next
-
带头结点的指针更好操作。在函数中,创建一个带头结点指针更方便操作。
node = ListNode(None)
使用场景:删除节点,翻转节点 -
链表取奇偶很简单,next的next就能保证奇偶