欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

5-数据结构单链表分析与java代码实现(腾讯、新浪面试题)

程序员文章站 2022-06-06 20:40:33
...

尚硅谷韩顺平Java数据结构与算法

链表(Linked List)


链表介绍和内存存储

  • 链表是有序的列表;内存中存储不一定连续
  • 链表是以节点方式来存储数据,链式存储
  • 每个节点包括data域,next域
  • 链表分带头节点的链表和不带头节点的链表,根据实际的需求来确定

5-数据结构单链表分析与java代码实现(腾讯、新浪面试题)

单链表

  • 单链表逻辑示意图
    5-数据结构单链表分析与java代码实现(腾讯、新浪面试题)

  • 单链表添加方法实现

    • 获取尾节点
      • 定义tail节点指向尾节点
      • 通过遍历列表获取尾节点
    • 将要插入的节点next复制为null(默认为null,可以不赋值)
    • 将尾节点的next域指向要插入的节点
  • 单链表顺序添加方法实现

    • 遍历链表,找到新节点要插入到的位置的前一个节点temp
    • 将新节点node.next = temp.next;
    • temp.next = node;
      5-数据结构单链表分析与java代码实现(腾讯、新浪面试题)
  • 单链表的删除方法实现

    • 遍历链表,找到要删除的节点的前一个节点temp
    • temp.next = temp.next.next;
  • 代码实现

 /**
  * 链表的节点:用于存储数据和next域
  */
 public class HeroNode {
     private int no;
     private String name;
     private String nickName;
     private HeroNode next;
 
     public HeroNode(int no, String name, String nickName) {
         this.no = no;
         this.name = name;
         this.nickName = nickName;
     }
 
     public void setName(String name) {
         this.name = name;
     }
 
     public void setNickName(String nickName) {
         this.nickName = nickName;
     }
 
     public int getNo() {
         return no;
     }
 
     public String getName() {
         return name;
     }
 
     public String getNickName() {
         return nickName;
     }
 
     public HeroNode getNext() {
         return next;
     }
 
     public void setNext(HeroNode next) {
         this.next = next;
     }
 
     @Override
     public String toString() {
         return "HeroNode{" +
                 "no=" + no +
                 ", name='" + name + '\'' +
                 ", nickName='" + nickName + '\'' +
                 '}';
     }
 }
 /**
  * 链表功能实现类
  */
 public class SingleLinkedList {
     private final HeroNode head = new HeroNode(0,"",""); //头节点,不存储数据
     private HeroNode tail = head; // 指向当前尾节点
 
     /**
      * 添加节点
      * @param node
      */
     public void add(HeroNode node){
         //1-获取尾节点
         tail.setNext(node);
         //3-将尾节点的next赋值为当前节点
         tail = node;
         
         //方法二:不定义tail节点,直接通过遍历列表找到尾节点再添加节点
 //        HeroNode temp = head;
 //        while (true){
 //            if (temp.getNext() == null){
 //                break;
 //            }
 //            temp = temp.getNext();
 //        }
 //        temp.setNext(node);
     }
 
     /**
      * 排序添加节点
      * @param node
      */
     public void addBySort(HeroNode node) {
         HeroNode temp = head; // temp用来记录node要插入位置的前一个
         boolean flag = false; // 用来标识该节点是否存在
         //1-遍历链表找到node应该插入的位置,
         while (true){
             if (temp.getNext() == null){
                 //空表 可以直接返回
                 break;
             }
             //确认node插入的位置
             if(temp.getNext().getNo() > node.getNo()){
                 break;
             }else if ((temp.getNext().getNo() == node.getNo())){
                 flag = true; // 节点存在,不能添加
                 break;
             }
             temp = temp.getNext();
         }
         if (flag){
             System.out.println("当前节点存在不能添加");
         }else{
             node.setNext(temp.getNext());
             temp.setNext(node);
         }
     }
     /**
      * 遍历链表
      */
     public void list(){
         if (head.getNext() == null){
             System.out.println("链表为空");
             return;
         }
         HeroNode temp = head.getNext();
         while (true){
             System.out.println(temp);
             if (temp.getNext() == null){
                 break;
             }
             temp = temp.getNext();
         }
     }
 
     /**
      * 修改链表中的相同编号的节点数据,编号不能修改
      * @param node
      */
     public void update(HeroNode node){
         HeroNode temp = head.getNext();
         boolean flag = false;
 
         while(true){
             if (temp == null){
                 System.out.println("空表,没有节点可以修改");
                 return;
             }
 
             if (temp.getNo() == node.getNo()){
                 flag = true;
                 break;
             }
             temp = temp.getNext();
         }
         if (flag){
             //修改
             temp.setName(node.getName());
             temp.setNickName(node.getNickName());
         }else {
             System.out.printf("没有找到编号%d的节点\n",node.getNo());
         }
     }
 
 }
//测试类
public class TestDemo {
    @Test
    public void testLinkedList(){
        HeroNode node1 = new HeroNode(1,"宋江","及时雨");
        HeroNode node2 = new HeroNode(2,"林冲","豹子头");
        HeroNode node3 = new HeroNode(3,"李逵","黑旋风");
        SingleLinkedList list = new SingleLinkedList();
//        list.add(node1);
//        list.add(node2);
//        list.add(node3);
        list.addBySort(node3);
        list.addBySort(node2);
        list.addBySort(node3);
        list.addBySort(node1);
        list.list();
        System.out.println("修改后列表");
        list.update(new HeroNode(1,"江江","及时雨"));
        list.list();
        System.out.println("删除后列表");
        list.delete(1);
        list.list();
    }
}

当前节点存在不能添加
HeroNode{no=1, name=‘宋江’, nickName=‘及时雨’}
HeroNode{no=2, name=‘林冲’, nickName=‘豹子头’}
HeroNode{no=3, name=‘李逵’, nickName=‘黑旋风’}
修改后列表
HeroNode{no=1, name=‘江江’, nickName=‘及时雨’}
HeroNode{no=2, name=‘林冲’, nickName=‘豹子头’}
HeroNode{no=3, name=‘李逵’, nickName=‘黑旋风’}
删除后列表
HeroNode{no=2, name=‘林冲’, nickName=‘豹子头’}
HeroNode{no=3, name=‘李逵’, nickName=‘黑旋风’}

面试题

  • 腾讯面试题:实现单链表反转
 public void reverse(){
        //1-定义一个新的头节点reverseHead用来关联反转后的链表
        HeroNode reverseHead = new HeroNode(0,"","");
        HeroNode cur = head.getNext();  //用来标记当前节点
        HeroNode next ;
        if (head.getNext() == null || head.getNext().getNext() == null) {
            return;
        }
        //2-遍历链表 将head中的每个节点 赋值给reverseHead通过头插法实现链表反转
        while(cur != null){
            next =cur.getNext();
            cur.setNext(reverseHead.getNext());
            reverseHead.setNext(cur);
            cur = next;
        }
        //3-将reverseHead赋值给head
        head.setNext(reverseHead.getNext());
    }
  • 新浪面试题:查找单链表倒数第k节点
public void select(int k){
    if (head.getNext() == null){
        System.out.println("空表");
        return;
    }
    HeroNode cur = head.getNext();
    //k健壮性
    if (k<=0 || k>size){
        System.out.println("数据错误");
        return;
    }
    for (int i = 0; i < size-k ; i++) {
        cur = cur.getNext();
    }
    System.out.println(cur.toString());
}