链表
About 5 min
链表倒置
leetcode 206 -easy 链表倒置
这题必须秒杀双指针, 同时记住反转链表这个模板题
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
leetcode 92 -mid 部分反转链表 去头去尾倒置中间部分
这道题在 反转 的前提下加入了反转范围, 难度还是有的, 值得多做几遍, 尤其需要注意各个部分的有效划分
class Solution:
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
return_head = ListNode(next=head)
number = right - left
curr = return_head
while left - 1 > 0:
curr = curr.next
left -= 1
def reverse(head, number):
count = 0
pre = None
curr = head
temp_head = head
while curr and count <= number:
temp = curr.next
curr.next = pre
pre = curr
curr = temp
count += 1
temp_head.next = curr
return pre
ptr = reverse(curr.next, number)
curr.next = ptr
return return_head.next
leetcode 445 mid 用链表模拟两数相加
这也说明你的 大数相加 还没有理解透彻,
可以做一个栈, 这样就不用倒序链表
还有优化的地方:
- 原链表上修改
- 逻辑判断
function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
l1 = reverseLink(l1);
l2 = reverseLink(l2);
let carry = 0;
let dummy = new ListNode(0);
let curr = dummy;
while (l1 || l2 || carry != 0) {
let sum: number;
if (l1 && l2) {
sum = l1.val + l2.val + carry;
if (sum >= 10) {
carry = 1;
} else {
carry = 0;
}
l1 = l1.next;
l2 = l2.next;
} else if (l1) {
sum = l1.val + carry;
if (sum >= 10) {
carry = 1;
} else {
carry = 0;
}
l1 = l1.next;
} else if (l2) {
sum = l2.val + carry;
if (sum >= 10) {
carry = 1;
} else {
carry = 0;
}
l2 = l2.next;
} else if (carry != 0) {
sum = carry;
carry = 0;
}
let newNode = new ListNode(sum % 10);
curr.next = newNode;
curr = curr.next;
}
return reverseLink(dummy.next);
}
function reverseLink(head: ListNode) {
let pre = null;
let curr = head;
while (curr) {
let temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
删除倒数第 N 个节点模板题
leetcode 61 -mid 旋转链表 (把链表平移 N 个单位, 注意拼接)
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
return_ptr = ListNode(next=head)
end = return_ptr
count = 0
while end.next:
end = end.next
count += 1
k = k % count if count != 0 else 0
slow = return_ptr
fast = return_ptr
if k == 0:
return head
for i in range(k):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
temp = slow.next
slow.next = None
fast.next = return_ptr.next
return temp
链表删掉所有重复的节点 82 - mid (删除所有重复的节点)
这一题自己做了很久, 一直没想到 prev.next == curr: 这个判断条件来判断中间是否有元素改变,自己本来想的是声明一个变量来记录是否为重复元素, 结果没有做出来,同时这个 while():while() 循环自己也没有思考到, 这题是那种典型的一看就会一写就犯难, 值得多上手写几遍
感觉可以抽象出一个观点: 删除重复就用 whilewhile 循环
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
returnPtr = ListNode(next=head)
prev = returnPtr
curr = head
while curr:
while curr.next and curr.next.val == curr.val:
curr = curr.next
if prev.next == curr:
prev = prev.next
else:
prev.next = curr.next
curr = curr.next
return returnPtr.next
引入 duplicate 其实也没有很麻烦,
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
returnPtr = ListNode(next=head)
prev = returnPtr
curr = head
duplicate = False
while curr:
while curr.next and curr.next.val == curr.val:
curr = curr.next
duplicate = True
if not duplicate:
prev = prev.next
else:
prev.next = curr.next
duplicate = False
curr = curr.next
return returnPtr.next
看起来蠢却是最直观的 方法, 时刻都要尊重第一想法
function deleteDuplicates(head: ListNode | null): ListNode | null {
let dummy = new ListNode(0, head);
let curr = dummy;
while (curr.next && curr.next.next) {
while (
curr.next.val == curr.next.next.val &&
curr.next.next.next &&
curr.next.next.val == curr.next.next.next.val
) {
curr.next.next.next = curr.next.next.next.next;
}
if (curr.next.val == curr.next.next.val) {
curr.next = curr.next.next.next;
} else {
curr = curr.next;
}
}
return dummy.next;
}
链表的遍历和条件构造
leetcode 86 mid 分隔列表 (把所有大于 x 的节点挑出来拼接)
这题的核心思路就是构造两条链表, 然后把他们拼起来,
这个思路不难, 但需要注意的是拼接后, 会有一段留尾, 需要单独把他们去除,
这里也凸显出来 dummy head 的重要性
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
returnPtr = ListNode(next=head)
sub_list = ListNode()
sub_curr = sub_list
curr = returnPtr
while curr.next:
if curr.next.val >= x:
sub_curr.next = curr.next
sub_curr = sub_curr.next
curr.next = curr.next.next
else:
curr = curr.next
if sub_curr.next and sub_curr.next.val < x:
sub_curr.next = None
curr.next = sub_list.next
return returnPtr.next
leetcode 725 分隔链表 mid (给一个链表和一个整数 K,返回一个被分割为 k 个部分的链表)
class Solution:
def splitListToParts(
self, head: Optional[ListNode], k: int
) -> List[Optional[ListNode]]:
length = self.link_length(head)
array = self.arrary_number(length, k)
print(array)
return_list = []
curr = head
for i in range(k):
dummy_node = ListNode(next=curr)
if array[i] != 0:
for j in range(array[i] - 1):
curr = curr.next
temp = curr.next
curr.next = None
curr = temp
return_list.append(dummy_node.next)
else:
return_list.append(None)
return return_list
def link_length(self, head):
curr = head
count = 0
while curr:
curr = curr.next
count += 1
return count
def arrary_number(self, length, k):
array = []
if (length % k) == 0:
for i in range(k):
array.append(length // k)
else:
res = length % k
for i in range(res):
array.append(length // k + 1)
for i in range(k - res):
array.append(length // k)
return array
leetcode 143 mid 重排链表 (S 型重排一个链表)
虽然做出来了, 但在前面找中点那里浪费了太多空间,
这样找中点会快很多
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next fast = fast.next.next
后续合并链表这样是不是更好些呢:
# Merge two halves
first = head
while second:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2
我的解决方案:
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
dummy_node = ListNode(next=head)
length = self.length_arr(head)
lengthA, lengthB = self.lengthAB(length)
curr = dummy_node
for i in range(lengthA):
curr = curr.next
listB = curr.next
curr.next = None
listA = dummy_node.next
listB = self.reverse(listB)
pre = listA
while listB:
temp = pre.next
pre.next = listB
listB = listB.next
pre.next.next = temp
pre = pre.next.next
return dummy_node.next
def reverse(self, head):
pre = None
curr = head
while curr:
temp = curr.next
curr.next = pre
pre = curr
curr = temp
return pre
def lengthAB(self, number):
return (number + 1) // 2, number // 2
def length_arr(self, head):
count = 0
curr = head
while curr:
curr = curr.next
count += 1
return count
ts 实现
function reorderList(head: ListNode | null): void {
let dummy = new ListNode(0, head);
let fast = dummy;
let slow = dummy;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}
let temp = slow.next;
slow.next = null;
let l2 = reverseList(temp);
let l1 = dummy.next;
while (l2) {
let templ2 = l2.next;
let temp = l1.next;
l1.next = l2;
l1.next.next = temp;
l1 = temp;
l2 = templ2;
}
}
function reverseList(head) {
let pre = null;
let curr = head;
while (curr) {
let temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
160. 相交链表 - 力扣（LeetCode）
题目描述：给你两个链表头，遍历两个链表，找到他们的第一个相交点（如果有的话）