共计 2969 个字符,预计需要花费 8 分钟才能阅读完成。
1.删除链表中的节点
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
现有一个链表 — head = [4,5,1,9],它可以表示为:
4 -> 5 -> 1 -> 9
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
说明:
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
思路:因为链表不是连续的内存,所以删除链表的节点,只需改变链表中该节点的上一节点的指针指向即可
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
next_node = node.next
node.val = next_node.val
node.next = next_node.next
2.删除链表的倒数第N个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
思路:建立一个新链表,l1和l2浅拷贝新链表,l1先从第一个节点访问到第n个节点,接着l1 和 l2 再同时扫描,当l1扫描到链表尾,l2就会到倒数第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:
res = ListNode(0)
res.next = head
l1 = res
l2 = res
# l1先扫描到第n个节点
for i in range(n):
l1 = l1.next
# l1 和 l2 同时扫描
while l1.next:
l1 = l1.next
l2 = l2.next
# 删除倒数第n个节点,因为是浅拷贝,操作的是res
l2.next = l2.next.next
return res.next
3.反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
思路:新建一个链表,扫描旧链表,每次只让旧链表的第I个元素插入到新链表的头部
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 空链表直接返回
if not head:
return head
cur,prev = head,None
while cur:
temp = cur.next #临时节点,用来暂存当次循环旧链表的下一个节点
cur.next = prev #把当前节点的next指向新链表
prev = cur #将prev指向新链表的头节点
cur = temp #将cur指向旧链表的下一个节点
return prev
4.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
思路:新建一个链表,依次扫描l1 和 l2,取小的值放入新链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
new_list = head
while l1 != None and l2 != None:
if l1.val < l2.val:
head.next = l1
l1 = l1.next
else:
head.next = l2
l2 = l2.next
head = head.next # 每次循环,都把head指向新链表的尾节点
# 走到这说明l1或者l2有一个已经遍历完了,剩下的就不需要排序了
if l1 != None:
head.next = l1
elif l2 != None:
head.next = l2
return new_list.next
5.回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
思路:依次取出链表的值,放到新的list里,判断这个list是否正序逆序相等(回文)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
_list = []
while head:
_list.append(head.val)
head = head.next
return _list == _list[::-1]
6.环形链表
给定一个链表,判断链表中是否有环。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
思路:快慢指针,快指针走两步,慢指针走一步,如果是环形,一定会相遇
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if head is None:
return False
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
以上是LeetCode 上的链表题,原题传送门:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/41/