day3 | 203. 移除链表元素，206. 反转链表，707. 设计链表

标签：index 203 cur val self next 链表 移除 节点

203. 移除链表元素

 

题目描述

 

给你一个链表的头节点head和一个整数val，删除链表中的那些存储的值为val的节点，并且返回新的头节点。

 

思路：

 

1. 创建一个虚拟头节点，取名为ptr1，指向head，另外再创建一个节点cur和ptr1相等，也指向head

2. 利用cur进行遍历，这里cur最开始并不能取为head，而是应该取为虚拟头节点，是因为当链表为空时，头节点是null，并没有next属性，会报错，而虚拟头节点有next属性，可以指向None或者指向null类型的。

3. 进入循环，不断判断cur所指向的下一个节点里面存的值是不是val，如果是，则把cur所指向的节点往后调一个。

4. 当下一个节点存的值不是val，就放心让cur成为下一个节点。

5. 因为cur从一开始就不存有val，那么一直变换下去，也不会存有val。

 

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        ptr1=ListNode(next=head)
        cur=ptr1
        while(cur.next!=None):
            if cur.next.val==val:
                cur.next=cur.next.next
            else:
                cur=cur.next
        return ptr1.next

 

 

206. 反转链表

 

题目描述

 

给你单链表的头节点head，请你反转链表，并返回反转后的链表的头节点

 

思路

 

代码如下

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre=None
        cur=head
        while(cur!=None):
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre

 

707. 设计链表

 

题目描述

 

 

 

思路

 

 

代码如下

class MyLinkedList:

    def __init__(self):
        self.dummy=ListNode() # 定义头节点，指向None
        self.count_node=0

    def get(self, index: int) -> int:
        if index<0 or index>=self.count_node: # 链表下标从0开始，所以当index取n，实际上有n+1个点
            return -1
        cur=self.dummy.next
        for _ in range(index):
            cur=cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0,val)



    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.count_node,val)


    def addAtIndex(self, index: int, val: int) -> None:
        if index>self.count_node:
            return
        pre=self.dummy
        for _ in range(index): # 循环1次，指向第0个节点；循环index次，指向第index-1个节点
            pre=pre.next
        pre.next=ListNode(val,pre.next) # pre指向一个新的节点，而这个新的节点的值为val，并指向pre节点原来指向的节点
        self.count_node+=1
        


    def deleteAtIndex(self, index: int) -> None:
        if index>=self.count_node:
            return
        pre=self.dummy
        for _ in range(index):
            pre=pre.next

        t=pre.next # t指向第index个节点
        pre.next=t.next # 用pre接收第index节点指向的下一个位置上的节点
        t.next=None
        self.count_node-=1 


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

 

 

 

 

 

 

 

 

 

总结

 

1. 熟练掌握虚拟头节点

2. 掌握next和value的含义

3. 掌握链表是怎么连起来的

标签：index,203,cur,val,self,next,链表,移除,节点
From： https://www.cnblogs.com/cp1999/p/17228111.html