160.相交链表
题目链接
解题思路
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if headA == None or headB == None:
return None
pA = headA
pB = headB
while pA != pB:
pA = headB if pA is None else pA.next
pB = headA if pB is None else pB.next
return pA
206.翻转链表
题目链接
解题思路
# 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, None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
234.回文链表
题目链接
解题思路
一共分为两个步骤:
- 复制链表值到数组列表中。
- 使用栓指针法判断是否为回文。
第一步,我们需要遍历链表将值赋值到数组列表中。我们用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 = head
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1]
141.环形链表
题目链接
解题思路
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
142.环形链表二
题目链接
解题思路
- 令fast重新指向链表头部节点。此时f = 0, s = nb。
- slow和fast同时每轮向前走1步。
- 当fast指针走到f = a步时,slow指针走到s = a + nb步。此时两只真重合,并同时指向链表环入口,返回slow指向的节点即可。
解题代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast, slow = head,head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next,slow.next
if fast == slow: break
fast = head
while fast != slow:
fast,slow = fast.next, slow.next
return fast