单链表面试题

一：单链表面试题

1.求单链表中有效节点的个数：

public int getLength()
       {
           if (head.next==null)
           {
               return 0;
           }
           int length = 0;
           HeroNode temp = head;
           while (temp.next != null)
           {
               length++;
               temp = temp.next;
           }
           return length;
       }

2.查询单链表中倒数第k个节点

思路分析：

1. 首先得知道链表的长度：int length = getLength();

2. 计算倒数的个数和长度的差值+1就是求解的节点【为什么要+1，数组是从0开始】

3. 开始遍历，找到第三个节点就行

public void GetBackByOne(int k)
       {
           if (head.next == null)
           {
               Console.WriteLine("当前链表为空！");
           }
           int length = getLength();
           if (k>length||k<=0)
           {
               Console.WriteLine("您输入的个数超过了链表长度，无法查询！");
           }
           int num = length - k+1;
           int count = 0;
           HeroNode temp = head;
           for(int i=0;i<num;i++)
           { 
             temp=temp.next;
           }
          Console.WriteLine(temp);
       }

3.单链表的反转：

自己的傻吊思路：

将整个链表读取出来，重新创建一个新的链表，重新赋值

代码如下：

public void fanzhuan()
       {
           if (head.next == null)
           {
               Console.WriteLine("当前链表为空！");
           }
           HeroNode temp = head;
           List<HeroNode> list = new List<HeroNode>();
           while (temp.next != null)
           {
               if (temp.no!=0)
               {
                   list.Add(temp);
                   temp = temp.next;
               }
               else
               {
                   temp = temp.next;
               }
           }
           list.Add(temp);
           head.next = null;
           for (int i = list.Count-1; i >=0; i--)
           {
               list[i].next = null;
               add(list[i]);
           }
       }

大佬的思路：

1.先定义一个新的节点reverseHead=new HeroNode();

2.从头到尾遍历原来的链表，每遍历一个节点，并放在新的链表的最前端

3.原来的链表的head.next=reverseHead.next

代码如下：

public void fanzhuan2(HeroNode head)
      {
          if (head.next == null || head.next.next == null)
          {
              return;
          }
          HeroNode cur=head.next;//获取下一个节点
          HeroNode next = null;
          HeroNode reverseHead = new HeroNode(0, "", "");//新建一个节点
          while (cur.next != null)
          {
              next = cur.next;//取下一个节点
              change(ref reverseHead,cur);//插入新节点
              if (next == null)
              {
                  break;
              }
              cur = next;//遍历下个节点
          }
          change(ref reverseHead, next);
          //将头节点替换一下大功完成！！！
          head.next = reverseHead.next;
      }
      public void change(ref HeroNode reverseHead,HeroNode cur)
      {
          HeroNode next = null;
          next = reverseHead.next;
          reverseHead.next = cur;
          cur.next = next;
      }

4.从尾到头打印单链表

方式一：借助栈的特性，先进后出

public void Print()
       {
           if (head.next == null)
           {
               Console.WriteLine("当前链表为空！");
           }
           Stack<HeroNode> nodes = new Stack<HeroNode>();
           HeroNode temp = head.next;
           while (temp.next!=null)
           {
               nodes.Push(temp);
               temp = temp.next;
           }
           nodes.Push(temp);

           int count = nodes.Count;
           for (int i = 0; i < count; i++)
           {
               Console.WriteLine(nodes.Pop());
           }
       }

方式二：

思路：

逆向打印单链表

1. 先将单链表进行反正操作，然后在便利即可；【会破坏原链表的结构，不可取】参考上面3即可

5.合并两个有序的单链表，合并之后的链表依然有序

public void hebing(SingleLinkedList reverseHead,ref SingleLinkedList reverseHead2)
{
    HeroNode hero = reverseHead.getHead().next;
    reverseHead2.add(hero);
}

6.代码地址：

Github地址