数据结构与算法之链表 链表经典题 大厂面试高频

数据结构与算法阿木 发布于 6 天前 2 次阅读


链表经典题(大厂面试高频)

链表是数据结构中的一种,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表在计算机科学中应用广泛,特别是在需要动态数据结构的情况下。本文将围绕链表这一主题,探讨一些经典的面试题目,这些题目在大厂面试中高频出现。

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个节点。这些题目在面试中经常出现,掌握这些题目的解题思路和代码实现对于面试者来说至关重要。希望本文能帮助读者更好地理解和解决链表相关的问题。