链表01-增删查改

Posted on Edited on

移除链表元素

如何移除链表的节点我这里不再过多赘述，之所以要特意为此写一篇博客是想重新认识一下虚拟头节点的作用

在没有虚拟头节点的情况下，删除链表中的元素有两种情况

  • 删除头节点
  • 删除非头节点
1
2
3
4
5
# 删除头节点
head=head.next

#删除非头节点
current.next=current.next.next

其实主要的原因就是 我们链表删除一个节点通常是通过修改上一个节点的指针对象，而头节点本身作为第一个节点，没有上一个节点，因此需要特殊处理

没有虚拟头节点的链表在删除操作中都需要进行一次头节点的特判

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while head and head.val==val:
        	head=head.next
        
        """
       		提醒一下，我一开始错误的直接对链表进行遍历
       		然后单独判断头节点，忘记考虑target节点是允许重复出现的
       		比如val=3   链表 3->3->3->4
       		所以一定要删干净  不能找到一个target删了就溜之大吉
       		下面同理
        """

        // 删除非头结点
        current=head
        while current.next:
        	if current.next.val==val:
        		current.next=current.next.next
        	else:
        		cureent=current.next
        return head
   
        
    }
};

设计链表

函数一：get(index)

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

需要特别注意一下的是链表的小标是从0开始的

1
2
3
4
5
6
7
8
9
10
def get(self,index):
    
    # 养成特判的好习惯
    if index <0 or index >self.size -1:
        return -1
    
    current=dummy_head.head
    for i in range(index):
        current=current.next
   	return current.val

函数二：addAtIndex(index,val)

在链表中的下标为index节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点

只要我们使用了虚拟头节点 那么插入操作和移除操作都无需特判头节点的操作

1
2
3
4
5
6
7
8
9
def addAtIndex(index,val):
	if index <0 or index >self.size:   # 注意本题特意强调了index等于链表长度的情况！
        return 
    
    current=dummy_head
    for i in range(index):
        current=current.next
   	current.next=ListNode(val,next=current.next)
	self.size+=1 			 # 一定不要忘记 删除增加都需要对size手动修改！

函数三 :deleteAtIndex(index)

在链表中删除下标为index的节点

1
2
3
4
5
6
7
8
9
10
def deleteAtIndex(index):
    if index <0 or index >self.size-1:
        return 
    
    current=dummy_head
    for i in range(index):
        current=current.next
    current.next=current.next.next
    self.size-=1

力扣上有原题 想复习链表的基础操作写这一题足矣

[力扣 链表设计](707. 设计链表 - 力扣（LeetCode）)