# 二刷力扣--链表

## 链表

class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next


### 移除链表元素 203.

#链表删除 #哑节点

class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
pre = dummy
cur = dummy.next
while cur:
if cur.val == val:
pre.next = cur.next
cur = cur.next
else:
pre = pre.next
cur = cur.next

return dummy.next


Python有垃圾回收，不需要手动删除节点。

### 设计链表 707.

class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def __init__(self):
self.dummy = Node(-1, None)
self.max_index = -1

def get(self, index: int) -> int:
if index < 0 or index > self.max_index:
return -1
cur = self.dummy.next
for  i in range(index):
cur = cur.next
return cur.val

self.dummy.next  = Node(val, self.dummy.next)
self.max_index += 1

def addAtTail(self, val: int) -> None:
cur = self.dummy
while cur.next:
cur = cur.next
cur.next = Node(val)
self.max_index += 1

def addAtIndex(self, index: int, val: int) -> None:
if  index < 0 or index > self.max_index + 1:
return
cur = self.dummy
i = 0
for i in range(index):
cur = cur.next

cur.next = Node(val, cur.next)
self.max_index += 1

def deleteAtIndex(self, index: int) -> None:
if  index < 0 or index > self.max_index:
return
cur = self.dummy
for i in range(index):
cur = cur.next

cur.next = cur.next.next
self.max_index -= 1


### 反转链表 206.

#双指针

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
while cur:
temp = cur.next # 下一个节点
cur.next  = pre # 反转next方向

pre = cur
cur = temp # 去下一个

return pre


### 两两交换链表中的节点 24.

#哑节点

class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy
# 交换cur后面的两个节点
while cur.next and cur.next.next:
node1 = cur.next
node2 = node1.next
node3 = node2.next
#  cur->node1->node2-->node3(node2.next)  ----> cur->node2->node1-->node3(node2.next)
cur.next = node2
node2.next = node1
node1.next = node3

cur = node1

return dummy.next


### 删除链表的倒数第N个节点 19.

#双指针 #哑节点

class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fast = dummy
slow = dummy
# 当fast 到达倒数第1个节点， slow到达倒数第n+1个节点
for i in range(n):
fast = fast.next
while fast.next :
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next


### 链表相交 面试题 02.07. 同 160

#双指针

class Solution:
length = 0
length += 1
return length

for _ in range (abs(lengthA- lengthB)):
Long = Long.next
while Short:
if Short == Long:
return Short
else:
Short = Short.next
Long = Long.next
return None



### 环形链表II 142.

#集合 #双指针

1. 直接用set记录访问过的节点，再次遇到则表明出现了环。
cla

fast一次走两个节点，所以走过的节点数是slow的两倍，即 x+y+n(y+z) = 2（x+y)。 化简一下，得到 x = (n-1)(y+z) + z

n = 1时， x = z 也就是说，一个指针index1从slow与fast相遇点出发，一个指针index2从头节点出发，会在入口节点相遇。

n大于1时和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点

class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
while fast and fast.next:
slow = slow.next
fast = fast.next.next

if slow == fast:
index1 = fast
while index1 != index2:
index1 = index1.next
index2 = index2.next
return index2

return None


## 链表小结

|
21天前
|
Java

16 2
|
21天前
|
Java

11 1
|
21天前
|

13 1
|
1月前
|

[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
1月前
|

19 3
|
1月前
|

11 1
|
1月前

14 1
|
1月前

14 1
|
1月前
|

11 1
|
1月前
|

18 1