328. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
# 边界条件判定
if not head or not head.next or not head.next.next:
return head
# 奇数头节点
jishu = head
isjishu = True # 标记奇数位
# 先保存偶数头节点
oushu0 = head.next
# 偶数头节点
oushu = head.next
cur = head.next.next
while cur:
# 先把相邻的奇数位、偶数位链表挑选出来
if isjishu:
jishu.next = cur
jishu = cur
else:
oushu.next = cur
oushu = cur
# 用于判断奇数位是否结束
isjishu = not isjishu
cur = cur.next
# 最后将奇数位链表的最后一个节点与偶数位链表的头节点相连
jishu.next = oushu0
# 偶数位链表最后一位与空相连
oushu.next = None
return head
234. 回文链表
输入：head = [1,2,2,1]
输出：true
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 辅助数据按顺序存储链表元素
items = []
cur = head
while cur:
items.append(cur.val)
cur = cur.next
return items == items[::-1]
61. 旋转链表
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
解释：[1,2,3,4,5]==>[5,1,2,3,4]==>[4,5,1,2,3]
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next or k == 0:
return head
# 把尾部的k个节点放在最前面
# 链表长度
count = 1
cur = head
while cur.next:
count += 1
cur = cur.next
# 反向链接
cur.next = head
# 旋转次数,前t个链表移动到后面
t = count - k % count
while t > 0:
cur = cur.next
t -= 1
# 新的头节点
newhead = cur.next
# 断开节点
cur.next = None
return newhead
19. 删除链表的倒数第 N 个结点
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 双指针
dummy = ListNode(0,head) # 哑结点
slow = dummy
fast = head
for i in range(n): # slow和fast中间相隔两个 n 个结点
fast = fast.next
while fast is not None: # 当fast到达末尾，slow所指的下一个节点将被删除
slow = slow.next
fast = fast.next
# 删除节点元素
slow.next = slow.next.next
return dummy.next
876. 链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 使用快慢指针
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 1 使用辅助数组
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
l = [head]
while l[-1].next:
l.append(l[-1].next)
return l[len(l)//2]
# 2 先获取链表的长度n，之后遍历到 n//2为止
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
n = 0
tmpnode = head
while tmpnode:
tmpnode = tmpnode.next
n += 1
i = 0
cur = head
while i < n//2:
cur = cur.next
i += 1
return cur
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 方法1：使用一个哈希表
# 思路：使用一个哈希表来存储所有已经访问过的节点，如果该节点存在于哈希表中，则说明该链表是环形链表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
# # 方法2：快慢指针
# # 思路：快指针每次移动一步，慢指针每次移动两步，如果快指针追上慢指针，则为环形链表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 边界条件
if head == None or head.next == None:
return False
# 快慢指针
slow = head
fast = head.next
while slow != fast:
if fast == None or fast.next == None:
return False
slow = slow.next # 每次走一步
fast = fast.next.next # 每次走两步
return True
21. 合并两个有序链表
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
prevHead = ListNode(-1)
prev = prevHead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
if l1 is not None:
prev.next = l1
else:
prev.next = l2
return prevHead.next
142. 环形链表 II
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = head
fast = head
while True:
if fast == None or fast.next == None:
return None
slow = slow.next
fast = fast.next.next
if slow == fast:
break
ans = head
while ans != slow:
ans = ans.next
slow = slow.next
return ans
160. 相交链表
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 思路：采用双指针，分别指向两链表的头节点
# 指针A先遍历完链表headA,再开始遍历headB
# 指针B先遍历完链表headB,再开始遍历headA
A, B = headA, headB
while A != B:
A = A.next if A else headB
B = B.next if B else headA
return A
网友评论