链表经典题(大厂面试高频)
链表是数据结构中的一种,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表在计算机科学中应用广泛,特别是在需要动态数据结构的情况下。本文将围绕链表这一主题,探讨一些经典的面试题目,这些题目在大厂面试中高频出现。
1. 链表概述
在开始之前,我们先简单回顾一下链表的基本概念:
- 节点:链表的基本组成单元,包含数据和指向下一个节点的指针。
- 头节点:链表的第一个节点,通常不存储数据。
- 尾节点:链表的最后一个节点,其指针指向`null`。
- 循环链表:链表的最后一个节点的指针指向头节点或某个中间节点。
2. 经典面试题目
2.1 反转链表
题目描述:给定一个单链表的头节点,反转整个链表。
思路:使用三个指针,分别指向当前节点的前一个节点、当前节点和下一个节点。遍历链表,不断调整指针,实现链表反转。
代码实现:
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
2.2 合并两个有序链表
题目描述:给定两个有序链表的头节点,合并它们为一个新的有序链表。
思路:使用两个指针分别遍历两个链表,比较当前节点值,将较小的节点添加到新链表中,并移动指针。
代码实现:
python
def merge_two_lists(l1, l2):
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
2.3 删除链表的倒数第N个节点
题目描述:给定一个链表和一个整数N,删除链表的倒数第N个节点。
思路:使用两个指针,一个指针先走N步,然后两个指针同时移动,当先走的指针到达链表末尾时,后走的指针指向的节点即为倒数第N个节点。
代码实现:
python
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
2.4 链表中的环
题目描述:给定一个链表,判断链表中是否存在环,并找出环的入口节点。
思路:使用快慢指针,快指针每次移动两步,慢指针每次移动一步。如果链表中存在环,快慢指针最终会相遇。然后,将其中一个指针移到链表头部,两个指针同时移动,相遇点即为环的入口节点。
代码实现:
python
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
2.5 链表中的第K个节点
题目描述:给定一个链表和一个整数K,返回链表中第K个节点的值。
思路:使用两个指针,一个指针先走K-1步,然后两个指针同时移动,当先走的指针到达链表末尾时,后走的指针指向的节点即为第K个节点。
代码实现:
python
def find_kth_to_last(head, k):
fast = slow = head
for _ in range(k):
if not fast:
return None
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
return slow.val
3. 总结
本文介绍了链表的一些经典面试题目,包括反转链表、合并两个有序链表、删除链表的倒数第N个节点、链表中的环和链表中的第K个节点。这些题目在面试中经常出现,掌握这些题目的解题思路和代码实现对于面试者来说至关重要。希望本文能帮助读者更好地理解和解决链表相关的问题。
Comments NOTHING