Skip to content

Commit 21f01d3

Browse files
daachengdaacheng
committed
更新md
更新md
1 parent 66ace77 commit 21f01d3

File tree

5 files changed

+118
-1
lines changed

5 files changed

+118
-1
lines changed

‎leetcode_linked_list/main.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
## LeetCode链表
22
1. [合并两个有序链表*](合并两个有序链表.md)
33

4-
2. [删除排序链表中的重复元素*](删除排序链表中的重复元素.md)
4+
2. [删除排序链表中的重复元素（单个指针）](删除排序链表中的重复元素.md)
55
3. [环形链表](环形链表.md)
6+
4. [相交链表](相交链表.md)
7+
5. [移除链表元素（两个指针）](移除链表元素.md)

‎leetcode_linked_list/相交链表.md‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
## 相交链表
2+
编写一个程序，找到两个单链表相交的起始节点。
3+
![](../pic/leetcode_linked_list/linkelist1.png)
4+
5+
#### 代码
6+
##### 迭代法
7+
把A链表的每个节点保存在字典中，迭代B链表，如果节点存在字典中，则就是相交的起始节点。
8+
9+
```python
10+
class ListNode:
11+
def __init__(self, val=0, next=None):
12+
self.val = val
13+
self.next = next
14+
15+
def __str__(self):
16+
var_list = []
17+
var_list.append(self.val)
18+
while self.next:
19+
var_list.append(self.next.val)
20+
self = self.next
21+
return '->'.join([str(item) for item in var_list])
22+
23+
24+
def getIntersectionNode(headA, headB):
25+
if not headA or not headB:
26+
return None
27+
28+
node_dict = {id(headA): None}
29+
while headA.next:
30+
node_dict[id(headA.next)] = None
31+
headA = headA.next
32+
33+
while headB:
34+
if id(headB) in node_dict:
35+
return headB
36+
headB = headB.next
37+
38+
return None
39+
```
40+
41+
##### 双指针
42+
* 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
43+
* 如果 pA 到了末尾，则 pA = headB 继续遍历
44+
* 如果 pB 到了末尾，则 pB = headA 继续遍历
45+
* 遍历的长度就是 A+B的长度
46+
* 如果两个链表不相交，最后肯定是pA pB同时为None
47+
* 如果两个链表相交，那么相交点之后的长度是相同的
48+
* 我们需要做的事情是，让两个链表从距离末尾节点同等距离的位置开始遍历，消除链表的长度差。
49+
* 比较长的链表指针指向较短链表head时，长度差就消除了
50+
51+
![](../pic/leetcode_linked_list/linkedlist2.png)
52+
53+
```python
54+
class Solution:
55+
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
56+
if not headA or not headB:
57+
return None
58+
prevA = headA
59+
prevB = headB
60+
61+
while prevA or prevB:
62+
if not prevA:
63+
prevA = headB
64+
if not prevB:
65+
prevB = headA
66+
if prevA == prevB:
67+
return prevA
68+
prevA = prevA.next
69+
prevB = prevB.next
70+
return None
71+
```

‎leetcode_linked_list/移除链表元素.md‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
## 移除链表元素
2+
删除链表中等于给定值 val 的所有节点。
3+
#### 示例
4+
```python
5+
输入: 1->2->6->3->4->5->6, val = 6
6+
输出: 1->2->3->4->5
7+
```
8+
9+
#### 代码
10+
哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。
11+
12+
```python
13+
# 原链表
14+
1->2->6->3->4->5->6
15+
# 添加哨兵节点
16+
0->1->2->6->3->4->5->6
17+
18+
# 当前节点指向1，前继节点指向哨兵节点0
19+
# 如果当前节点为要删除节点，前继节点.next = 当前节点.next,当前节点后移
20+
# 如果当前节点不是要删除的节点，前继节点 = 当前节点，当前节点后移
21+
22+
```
23+
24+
* 初始化哨兵节点为 ListNode(0) 且设置 sentinel.next = head。
25+
* 初始化两个指针 curr 和 prev 指向当前节点和前继节点。
26+
* 当前节点不为None时，比较当前节点与目标值，如果相等，则prev.next = curr.next;如果不相等prev = curr
27+
* 遍历下一个元素：curr = curr.next
28+
29+
```python
30+
def removeElements(head, val):
31+
sentinel = ListNode(0)
32+
sentinel.next = head
33+
34+
prev = sentinel # 前继节点
35+
cur = head # 当前节点
36+
37+
while cur:
38+
if cur.val == val:
39+
prev.next = cur.next
40+
else:
41+
prev = cur
42+
cur = cur.next
43+
return sentinel.next
44+
```

‎pic/leetcode_linked_list/linkedlist2.png‎

110 KB
Loading

‎pic/leetcode_linked_list/linkelist1.png‎

19.3 KB
Loading

0 commit comments

Comments
 (0)