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

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

链表(Linked List)

---

链表介绍和内存存储

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

单链表

• 单链表逻辑示意图
  

• 单链表添加方法实现

  • 获取尾节点
    • 定义tail节点指向尾节点
    • 通过遍历列表获取尾节点
  • 将要插入的节点next复制为null(默认为null，可以不赋值)
  • 将尾节点的next域指向要插入的节点

• 单链表顺序添加方法实现

  • 遍历链表，找到新节点要插入到的位置的前一个节点temp
  • 将新节点node.next = temp.next;
  • temp.next = node;
    

• 单链表的删除方法实现

  • 遍历链表，找到要删除的节点的前一个节点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());
}