Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

代码的鲁棒性:链表中倒数第k个结点

lingfeng95 2019-07-22 13:51:00 阅读数:17 评论数:0 点赞数:0 收藏数:0

题目描述

输入一个链表,输出该链表中倒数第k个结点。例如:输入一个链表,输出该链表中倒数第k个结点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾结点是倒数第1个结点。例如一个链表有6个结点,从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

解题思路

寻常的解法,找到链表的长度n,通过长度找到倒数第k个节点的位置n-k+1,之后遍历找到结果,这个方法的效率是2n,这里不用这种方法,这里用双指针的方法实现。
1.第一个指针从链表的头指针开始遍历k-1个节点,第二个指针不动
2.从k步开始,第二个指针也开始从链表的头指针开始遍历
3.由于两个指针始终保持k-1,当第一个指针到达链表结尾的时候,第二个指针也正好到达倒数第k个节点。

鲁棒性:鲁棒是Robust的音译,也就是健壮和强壮的意思,它是在异常和危险情况下系统生存的关键。比如说,计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下,能否不死机、不崩溃,就是该软件的鲁棒性。

这个题中有三处鲁棒性:
1.节点为空
2.总节点数小于k
3.k小于0

代码实现

/// <summary>
    /// 链表
    /// </summary>
    public class ListNode
    {
        public int item;
        public ListNode next;
        public ListNode(int x)
        {
            item = x;
        }

        /// <summary>
        /// 生成链表
        /// </summary>
        /// <param name="length"></param>
        public static ListNode CreateNodeList(int length)
        {
            ListNode listNode = new ListNode();
            var temp = listNode;
            for (int i = ; i < length; i++)
            {
                temp = nextList(temp, i);
            }

            return listNode;

            //下一个
            ListNode nextList(ListNode node, int value)
            {
                while (node.next != null)
                {
                    node = node.next;
                }
                var next = new ListNode(value);
                node.next = next;
                return next;
            }
        }
    }
View Code
        public static ListNode FindBackKth(ListNode node, int k) {
            if (node == null || k <= ) {
                return null;
            }

            ListNode firstNode = node;
            ListNode secondNode = node;
            for (int i = ; i <= k - ; i++) {
                firstNode = firstNode.next;
                if (firstNode == null) {
                    return null;
                }
            }

            while (firstNode.next != null) {
                firstNode = firstNode.next;
                secondNode = secondNode.next;
            }

            return secondNode;
        }

测试

[Fact]
        public void TestNull()
        {
            ListNode listNode = null;
            Assert.Null(Coding014.FindBackKth(listNode,));
        }

        [Fact]
        public void TestK()
        {
            ListNode listNode = new ListNode();
            Assert.Null(Coding014.FindBackKth(listNode, ));
            Assert.Equal(, Coding014.FindBackKth(listNode, ).item);
            Assert.Null(Coding014.FindBackKth(listNode, ));
        }

        [Fact]
        public void Test1()
        {
            //0,1,2,3,4,5
            ListNode listNode = ListNode.CreateNodeList();
            Assert.Null(Coding014.FindBackKth(listNode, ));
            Assert.Null(Coding014.FindBackKth(listNode, ));
            Assert.Equal(, Coding014.FindBackKth(listNode, ).item);
            Assert.Equal(, Coding014.FindBackKth(listNode, ).item);
            Assert.Equal(, Coding014.FindBackKth(listNode, ).item);
        }
View Code

 

版权声明
本文为[lingfeng95]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/zhao123/p/11225402.html