单链表以及常见算法题

单链表简单介绍

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表的实现

实现单链表的添加、更新、删除、遍历、获取链表长度等方法
首先定义一个节点类HereNode，

//定义HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    //指向下一个节点
    public HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    public HeroNode(int no, String name, String nickname, HeroNode next) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

/**
 * 定义SingleLinkedList 管理我们的英雄
 */
class SingleLinkedList {
    /**
     * 先初始化一个头节点
     */
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加
     * 思路，不考虑编号顺序时
     * 1、找到当前链表的最后节点
     * 2、将最后这个节点的 next 指向新节点
     */
    public void add(HeroNode heroNode) {
        HeroNode temp = head;
        while (temp.next != null) {
            //退出循环时，指向链表最后
            temp = temp.next;
            if (temp.no==heroNode.no) {
                System.out.println("这个排名："+heroNode.no+"已经存在了");
                return;
            }
        }
        temp.next = heroNode;
    }

    /**
     * 第二种添加方式，根据排名将英雄插入到指定位置
     * 根据id大小顺序添加，如果id重复，则无法添加
     */
    public void addById(HeroNode heroNode) {
        HeroNode temp = head;

        while (temp.next != null) {
            if (heroNode.no == temp.next.no) {
                System.out.printf("已存在该排名：%d\n", heroNode.no);
                return;
            } else if (heroNode.no < temp.next.no) {
                break;
            }
            temp = temp.next;
        }
        //此时的temp就说我们想插入的位置的
        heroNode.next = temp.next;
        temp.next = heroNode;
    }

    /**
     * 修改节点的信息，根据no编号来修改，即no编号不能改
     */
    public void update(HeroNode newHeroNode) {
        HeroNode temp = head.next;
        if (temp == null) {
            System.out.println("链表为空~");
            return;
        }
        //找到需要修改的节点
        boolean flag = false;
        while (temp != null) {
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //找到了该节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.println("没有找到排名为" + newHeroNode.no + "的英雄");
        }
    }

    /**
     * 删除
     */
    public void remove(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (temp.next != null) {
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        }else {
            System.out.println("没有排名为"+ no +"的英雄！");
        }
    }

    /**
     * 遍历
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

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

单链表的面试题

查找单链表中倒数第k个节点 【新浪面试题】

思路：

1. 单链表的长度-k+1，就是链表正序的位置，例如：链表长度为10，k为9，则正序位置为2，也就是第二个结点
2. 前提是 长度 - k >=0, 且 k不能小于等于0。

public HeroNode selectByK(int k){
	//getLength()为获取链表的长度，即有效元素个数
       if(k <= 0 && k > getLength()){
		throw new RuntimeException("K值："+k+"，不合法");
	}
	HeroNode temp = head;
	int index = getLength - k + 1;
	for(int i = 0; i < index; i++){
		temp = temp.next;
	}
	return temp;
   }

单链表的反转 【腾讯面试题】

思路：
定义一个新的链表，将旧链表（要反转的链表）的元素遍历，依次插入头结点的后面，并连接好头节点后面的原结点。最后新链表就是反转后的链表

/**
    * 单链表的反转 【腾讯面试题】 有点难度
    */
   public static SingleLinkedList reverse(SingleLinkedList oldList) {
       if (oldList.getLength() == 0) {
           return null;
       }
       if (oldList.getLength() == 1) {
           return oldList;
       }
       //定义一个新单向链表
       SingleLinkedList newList = new SingleLinkedList();
       //临时变量1，表示 旧链表的首个有效元素
       HeroNode temp = oldList.head.next;
       //临时变量2
       HeroNode temp2 = null;
       //遍历 旧链表
       while (temp != null) {
           //将旧链表的元素取出来
           temp2 = temp;
           //旧链表后移
           temp = temp.next;
           temp2.next = null;

           //将旧链表的元素依次放入新链表的头部的下一节点
           temp2.next = newList.head.next;
           newList.head.next = temp2;
       }
       return newList;
   }

逆序打印单向链表 【百度面试题】

思路1：使用栈这种数据结构进行存储

/**
    * 逆序打印单向链表 【百度面试题】
    */
   public void reversePrint() {
       HeroNode temp = head.next;
       if (temp == null) {
           //链表为空不打印
           return;
       }
       Stack<HeroNode> stack = new Stack<>();
       while (temp != null) {
           stack.push(temp);
           temp = temp.next;
       }

       while (stack.size() > 0) {
           System.out.println(stack.pop());
       }
   }

思路2：使用递归的方式

//使用递归
public void reversePrint2(HeroNode startNode){
       if (startNode == null) {
           return;
       }
       if (startNode.next != null) {
           reversePrint2(startNode.next);
       }
       if (startNode != head) {
           System.out.println(startNode);
       }
   }