leetcode-top100链表专题一

本文主要是介绍leetcode-top100链表专题一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

160.相交链表

题目链接

160. 相交链表 - 力扣（LeetCode）

解题思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:if headA == None or headB == None:return NonepA = headApB = headBwhile pA != pB:pA = headB if pA is None else pA.nextpB = headA if pB is None else pB.nextreturn pA

206.翻转链表

题目链接

206. 反转链表 - 力扣（LeetCode）

解题思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:cur, pre = head, Nonewhile cur:tmp = cur.nextcur.next = prepre = curcur = tmpreturn pre

234.回文链表

题目链接

234. 回文链表 - 力扣（LeetCode）

解题思路

一共分为两个步骤：

1. 复制链表值到数组列表中。
2. 使用栓指针法判断是否为回文。

第一步，我们需要遍历链表将值赋值到数组列表中。我们用currentNode指向当前节点。每次迭代向数组添加currentNode.val，并更新currentNode = currentNode.next，当currentNode = null时停止循环。

执行第二部的最佳方法取决于你使用的语言。在Python中，很容易构造一个列表的反向副本，也很容易比较两个列表。而在其他语言中，就没那个简单。因此最好使用双指针来检查是否为回文。我们在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，则返回false;相同则将两个指针向内移动，并继续判断，直至两个指针相遇。

在编码的过程中，注意我们比较的时节点值的大小，而不是节点本身，正确的比较方式是，node1.val == node2.val，而不是node1 == node2。

解题代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:vals = []current_node = headwhile current_node is not None:vals.append(current_node.val)current_node = current_node.nextreturn vals == vals[::-1]

141.环形链表

题目链接

141. 环形链表 - 力扣（LeetCode）

解题思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:seen = set()while head:if head in seen:return Trueseen.add(head)head = head.nextreturn False

142.环形链表二

题目链接

142. 环形链表 II - 力扣（LeetCode）

解题思路

1. 令fast重新指向链表头部节点。此时f = 0, s = nb。
2. slow和fast同时每轮向前走1步。
3. 当fast指针走到f = a步时，slow指针走到s = a + nb步。此时两只真重合，并同时指向链表环入口，返回slow指向的节点即可。

解题代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast, slow = head,headwhile True:if not (fast and fast.next): returnfast, slow = fast.next.next,slow.nextif fast == slow: breakfast = headwhile fast != slow:fast,slow = fast.next, slow.nextreturn fast

这篇关于leetcode-top100链表专题一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---