大前端

前端学习之家-大前端

力扣刷题:数组:Java:19:删除链表的倒数第N个结点

 

 力扣

0.前言

本帖是不成熟的代码记录

连暴力解法都算不上,扫描两次,仅供后续复习,不当之处请多指教

1、如何求带头结点链表的长度?

数据结构中由于链表的特殊结构性质,求链表的长度,要对链表进行遍历,且一定要遍历完

int cnt=0;
Node cur=head;//由于头指针不能变更,设置cur指示当前指向的结点

while(cur!=null)//此处一定要是cur,不能是cur.next,不然最后一个节点进不去,计不上数
{
    cnt++;
    cur=cur.next;
}

如本图所示,链表总共三个节点

cnt++两次,当进入第三次while循环的判定时,由于cur指向第三个结点,但是没有第四个结点

对第三个来说,cur.next=null

因此第三个记录不上!

遍历判定条件很重要!

2、本题暴力如何区别特殊情况

分析不难发现

1:删除的为倒数第一位,即最后一个
       1.1: 删除的为1,且链表长度为1,即把头结点指向空
        1.2: 删除的为最后一个,且链表长度大于1,即把倒数第二个结点的next域指向空
2:删除的不为倒数第一位
        2.1 该删除的结点左右都有结点
        2.2 删除的恰好是链表的第一个结点,头结点指向的,头节点指向原链表中的第二个。

 2.1:删除的为倒数第一位,即最后一个


       2.1.1: 删除的为1,且链表长度为1,即把头结点指向空

return head=null;


        2.1.2: 删除的为最后一个,且链表长度大于1,即把倒数第二个结点的next域指向空


2.2:删除的不为倒数第一位


       2. 2.1 该删除的结点左右都有结点

current=current.next.next;
//当前的current指向的是要删除的结点的左边的结点
//要删除的是current.next;
//要将他连接上 要删除的下一个,即:current.next.next;


        2.2.2 删除的恰好是链表的第一个结点,头结点指向的,头节点指向原链表中的第二个。

head=head.next;

3、源代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution 
{
    public ListNode removeNthFromEnd(ListNode head, int n) 
    {
        int cnt=0;//第一次扫描用
        int count=0;//第二次扫描用
        ListNode cur=head;//1
        ListNode current=head;//2
        while(cur!=null)//此处一定是当前指向为空啊,不然最后一个遍历进不去记录不上!
        {
            cnt++;
            cur=cur.next;
        }
        if(n==1)
        {
                if(cnt==1)
                {
                    head=null;
                    return head;
                }
        }
        if(n==1)
        {
            while(current!=null)
            {

                count++;
                if(count==cnt-1)
                {
                    current.next=null;
                    break;
                }
                current=current.next;
            }
            return head;
        }
        if(n!=1&&n==cnt)
        {
            head=head.next;
        }
        if(n!=1)
        {
            while(current!=null)
            {
                count++;
                if(count==cnt-n)
                {
                    current.next=current.next.next;
                    break;
                }
                current=current.next;
            }

        }
        return head;
    }
}

4、总结

带头结点的单链表 

此帖仅供后续精进优化,向着只扫描一次优化,冲鸭!

 

发表评论:

Copyright Your WebSite.Some Rights Reserved.