今天是day3,今天的内容如下：
第一题为移除链表元素，简而言之为，给定一个链表，要求删除所有值为val的节点并最终把头结点输出。
func removeelements(head *ListNode,val int) *ListNode {
for head!=nil && head.Val==val{
head = head.next
}
cur:=head
for cur!=nil && cur.Next!=nil{
if cur.Next.Val == val{
cur.Next = cur.Next.Next
}else{
cur = cur.Next
}
}
return head
}
法二虚拟头结点法：
func removeElements(head *ListNode,val int) *ListNode{
dummy:=&ListNode{}
dummy.Next = head
cur:=dummy
for cur!=nil && cur.Next!=nil{
if cur.Next.Val == val{
cur.Next =cur.Next.Next
}else{
cur = cur.Next
}
}
return dummy.Next
}
python虚拟头结点法：
class solution:
def removeElements(self,head:Option[ListNode],val:int) ->Option[ListNode]:
dummy_head = ListNode(next = head)
current = dummy_head
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy_head.next
第二题为构造链表以及定义相关方法：
用go语言实现:
type MyLinkedList struct{
dummy *Node
}
type Node struct{
Val int
Next *Node
Pre *Node
}
func Constructor() MyLinkedList {
rear := &Node{
Val:-1,
Next:nil,
Pre:nil,
}
rear.Next = rear
rear.Pre = rear
return MyLinkedList{rear}
}
func (this *MyLinkedList) Get(index int){
head = this.dummy.Next
for head!= this.dummy && index > 0{
index--
head = head.Next
}
if 0!= index {
return -1
}
return head.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
dummy:=this.dummy
node:=&Node{
Val:val,
Next:dummy.Next,
Pre:dummy,
}
dummy.Next.Pre = node
dummy.Next = node
}
func (this *MyLinkedList) AddAtTail(val int) {
dummy:=this.dummy
rear:=&Node{
Val:val,
Next:dummy,
Pre:dummy.Pre,
}
dummy.Pre.Next = rear
dummy.Pre = rear
}
func (this *MyLinkedList) AddAtIndex(index int,val int) {
head:=this.dummy.Next
for head != this.dummy && index > 0 {
head = head.Next
index--
}
if index > 0{
return
}
node:=&Node{
Val:val,
Next:head,
Pre:head.Pre,
}
head.Pre.Next = node
head.Pre = ndoe
}
func (this *MyLinkedList) DeleteAtIndex(index int){
if this.dummy.Next == this.dummy {
return
}
head := this.dummy.Next
for head.Next != this.dummy&&index >0 {
head = head.Next
index--
}
if index == 0{
head.Next.Pre = head.Pre
head.Pre.Next = head.Next
}
}
python版本：
class ListNode:
def __init__(self,val-0,prev=None,next=None):
self.val =val
self.prev = prev
self.next = next
class MyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def get(self,index:int) -> int:
if index < 0 or index >= index.size:
return -1
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index -1):
current = current.prev
return current.val
def addAthead(self,val:int) -> None:
new_node = ListNode(val,None,self.head)
if self.head:
self.head.prev = new_node
else:
self.tail = new_node
self.head = new_ndoe
self.size+=1
def addAtTail(self,val:int) -> None:
new_ndoe=ListNode(val,self.tail,None)
if self.tail:
self.tail.next = new_node
else:
self.head = new_node
self.tail = new_node
self.size+=1
def addAtindex(self,index:int,val:int)->None:
if index < 0 or index > self.size:
return
if index == 0:
self.addAthead(val)
elif index == self.size:
self.addAttail(val)
else:
if index < self.size // 2:
current = self.head
for i in range(index -1):
current = current.next
else:
current = self.tail
for i in range(self.size - index):
current = current.prev
new_node = ListNode(val,current,current.next)
current.next.prev = new_node
current.next = new_node
self.size+=1
def deleteAtindex(self,index:int) ->None:
if index < 0 or index >= self.size:
return
if index == 0:
self.head = self.head.next
if self.head:
self.head.prev = Noe
else:
self.tail = None
elif index == self.size - 1:
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None
else:
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index -1):
current = current.prev
current.prev.next = current.next
current.next.prev = current.prev
self.size-=1
题目三：反转链表，即在一个给定链表中，将其顺序反转
func reverseList(head *ListNode) *ListNode{
var pre *ListNode
cur:=head
for cur!=nil{
next:=cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
python版本：
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
python递归法：
class Solution:
def reverseList(self,head:Optional[ListNode]) ->Optipnal[ListNode]:
return self.reverse(head,None)
def reverse(self,cur:ListNode,pre:ListNode) -> ListNode:
if cur == None:
return pre
temp = cur.next
cur.next = pre
return self.reverse(temp,cur)