203.移除链表元素
203. 移除链表元素 - 力扣(LeetCode)
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。
示例 1:
- 输入:head = [1,2,6,3,4,5,6], val = 6
- 输出:[1,2,3,4,5]
示例 2: - 输入:head = [], val = 1
- 输出:[]
示例 3: - 输入:head = [7,7,7,7], val = 7
- 输出:[]
class Solution():
def ListNode(self,val=0,next=next):
self.val = val
self.next = next
def removeElements(self,head,val):
dummy_head = ListNode(next=head)
current = dummy_head
while current.next:
if current.next.val == val:
current.next = head.next
else:
current = current.next
head = head.next
return dummy_head.next
707.设计链表
707. 设计链表 - 力扣(LeetCode)
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性 prev
以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList
类:
MyLinkedList()
初始化MyLinkedList
对象。int get(int index)
获取链表中下标为index
的节点的值。如果下标无效,则返回-1
。void addAtHead(int val)
将一个值为val
的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)
将一个值为val
的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)
将一个值为val
的节点插入到链表中下标为index
的节点之前。如果index
等于链表的长度,那么该节点会被追加到链表的末尾。如果index
比长度更大,该节点将 不会插入 到链表中。void deleteAtIndex(int index)
如果下标有效,则删除链表中下标为index
的节点。
class ListNode():
def __init__(self, val=0, next=None):
self.val = val
self.next= next
class MyLinkedList():
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def get(self,index): # 判断index边界, 从虚拟头节点next开始
if index<0 or index>=self.size:
return -1
current = self.dummy_head.next
for _ in range(index):
current = current.next
return current.val
def addAtHead(self,val):
self.dummy_head.next = ListNode(val=val, next=self.dummy_head.next)
self.size += 1
def addAtTail(self,val):
current = self.dummy_head
while current.next:
current = current.next
current.next = ListNode(val=val,next=current.next)
self.size += 1
def addAtIndex(self,index,val):
if index<0 or index>self.size: # index==链表长度, 插入尾节点
return
current = self.dummy_head
for _ in range(index):
current = current.next
current.next = ListNode(val=val, next=current.next)
self.size+=1
def deleteAtIndex(self,index):
if index<0 or index>=self.size:
return
current = self.dummy_head
for _ in range(index):
current = current.next
current.next = current.next.next
self.size-=1
206.反转链表
206. 反转链表 - 力扣(LeetCode)
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例1:
- 输入:head = [1,2,3,4,5]
- 输出:[5,4,3,2,1]
示例2: - 输入:head = [1,2]
- 输出:[2,1]
示例 3: - 输入:head = []
- 输出:[]
解题思路:- 双指针:设定pre和cur,当cur不为None时,将cur.next->pre,再移动pre和cur
- 递归法:与双指针类似,只是将cur和pre赋值过程改为递归调用形式
class ListNode():
def __init__(self,val=0,next=None):
self.val=val
self.next=next
def reverstList(self,head): # 双指针
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
def reverseList(self,head): # 递归法(双指针形式)
return self.reverse(head,None)
def reverse(self,cur,pre):
if cur == None:
return pre
temp=cur.next
cur.next=pre
return self.reverse(temp,cur)
def reverseList(self,head): # 递归法(没理解太明白)
if head is None or head.next is None:
return head
new_head = reverseList(head.next)
head.next = head.next.next
head.next = None
return new_head