LeetCode链表相关问题总结

╰+哭是因爲堅強的太久メ 2021-11-02 07:46 241阅读 0赞

1.  获取链表的长度  
    两种方法
    
        ListNode frist = head;
        	int length = 0;
        
            // 先获得链表的长度
            while (frist != null) { 
                length++;
                frist = frist.next;
            }
    
    或者
    
        ListNode frist = head;
        	int length = 1;
        
            // 先获得链表的长度
            while (frist.next != null) { 
                length++;
                frist = frist.next;
            }
    
    区别就是使用第二种方法，空链表的时候会报`空指针异常`，第一种无妨，空链表的话长度得出就是0  
    但是第二种方法最后的frist就是链表的最后一个结点，而第一种方法最后的frist为null  
    所以他们各有利弊，选择使用即可
2.  在链表的最后拼接上该链表
    
        例：
        原链表：1->2->3->4->5
        之后：1->2->3->4->5->1->2->3->4->5
    
        ListNode frist = head;
        while (frist.next != null) { 	           
                    frist = frist.next;
                }
        	      
        frist.next = head;
    
    也就是遍历找到链表最后一个结点，然后让最后那个结点的next指向头结点即可
3.  查找指定位置的结点  
    我们都知道链表在内存中存储是不连续的单元，与数组不一样，查询的话，需要遍历整个链表
    
        // 这段代码实现根据索引获取到指定链表结点（索引从0开始，也就是头结点是0）
        for (int i = 0; i < index; i++) { 
                    head = head.next;
                }
4.  删除某个结点就是：  
    找到该节点的上一个结点`node`，令`node.next = node.next.next`
5.  新增一个结点就是：  
    找到需要新增结点node位置的上一个结点before，令`before.next = node` `node.next=before.next.next`

暂且这么多，遇到新的再补充