1、源码

Player实体类

  1. package com.study.linkedlist;
  3. public class Player {
  5.     public int no;
  6.     public String name;
  7.     public Player next;
  9.     public Player(int no, String name) {
  10.         this.no = no;
  11.         this.name = name;
  12.     }
  13.     public Player() {
  14.     }
  16.     @Override
  17.     public String toString() {
  18.         return "Player{" +
  19.                 "no=" + no +
  20.                 ", name='" + name + '\'' +
  21.                 '}';
  22.     }
  23. }

SingleLinkedList类

  1. package com.study.linkedlist;
  3. import java.util.HashSet;
  4. import java.util.Stack;
  6. public class SingleLinkedList {
  8.     //初始化头结点
  9.     private Player p = new Player(0,"");
  11.     public Player getP() {
  12.         return p;
  13.     }
  15.     //添加节点到链表中
  16.     //不考虑编号顺序
  17.     //1.找到当前链表的最后一个节点
  18.     //2.将最后节点的next指向新的节点
  19.     public void add(Player player){
  21.         //定义一个零时的头结点
  22.         Player temp = p;
  23.         //遍历链表，找到最后一个节点
  24.         while (true){
  25.             if(temp.next == null){
  26.                 break;
  27.             }
  28.             temp = temp.next;
  29.         }
  30.         temp.next=player;
  31.     }
  33.     //添加方法二：按顺序添加，并且添加编号相同的数据时提示添加错误
  34.     public void addByNo(Player player){
  36.         //定义一个零时的头结点
  37.         Player temp = p;
  38.         boolean flag = false;//定义一个标识，判断链表中是否已经存在相同的编号
  39.         while (true){
  40.             if (temp.next==null){
  41.                 break;
  42.             }
  43.             if (temp.next.no > player.no){
  44.                 break;
  45.             }else if (temp.next.no == player.no){
  46.                 flag = true;//说明编号存在；
  47.                 break;
  48.             }
  49.             temp = temp.next;
  50.         }
  51.         if (flag){
  52.             System.out.println("球员已经存在，不能加入"+temp.next.no+temp.next.name);
  53.         }else {
  54.             player.next = temp.next;
  55.             temp.next = player;
  56.         }
  57.     }
  59.     //根据编号修改球员信息
  60.     public void updateByNo(Player player){
  62.         //判断链表是否为空
  63.         if (p.next==null){
  64.             System.out.println("链表为空");
  65.             return;
  66.         }
  67.         Player temp = p.next;
  68.         boolean flag = false;
  69.         while (true){
  70.             if(temp.next==null){
  71.                 break;
  72.             }
  73.             if(temp.no==player.no){
  74.                 flag = true;
  75.                 break;
  76.             }
  77.             temp = temp.next;
  78.         }
  79.         if(flag){
  80.             temp.name= player.name;
  81.         }else {
  82.             System.out.println("没有找到改球员");
  83.         }
  84.     }
  86.     //根据编号删除节点
  87.     public void deleteByNo(int no){
  88.         //判断链表是否为空
  89.         if (p.next==null){
  90.             System.out.println("链表为空");
  91.             return;
  92.         }
  93.         Player temp = p.next;
  94.         boolean flag = false;
  95.         while (true){
  96.             if(temp.next==null){
  97.                 break;
  98.             }
  99.             if(temp.next.no==no){
  100.                 flag = true;
  101.                 break;
  102.             }
  103.             temp = temp.next;
  104.         }
  105.         if (flag){
  106.             temp.next = temp.next.next;
  107.         }else {
  108.             System.out.println("没有找到改球员");
  109.         }
  111.     }
  113.     //获取链节点的有效个数
  114.     public int getLength(Player p){
  115.         if (p.next==null){
  116.             System.out.println("链表为空");
  117.             return 0;
  118.         }
  119.         int length = 0;
  120.         Player temp = p.next;
  121.         while (temp!=null){
  122.             length++;
  123.             temp = temp.next;
  124.         }
  125.         return length;
  126.     }
  128.     //查找单链表中倒数第k个节点
  129.     public void getByNo(Player p,int no){
  130.         if (p.next==null){
  131.             System.out.println("链表为空");
  132.             return;
  133.         }
  134.         int l = getLength(p);
  135.         if (no<0 || no >l){
  136.             System.out.println("没有该节点");
  137.             return;
  138.         }
  139.         Player temp = p.next;
  140.         for (int i = 0; i < l - no; i++) {
  141.             temp = temp.next;
  142.         }
  143.         System.out.println("倒数第"+no+"个节点的数据为："+temp.no+temp.name);
  144.     }
  146.     //翻转链表
  147.     public void reverse(Player p){
  148.         if (p.next==null || p.next.next==null){
  149.             System.out.println("链表为空");
  150.             return;
  151.         }
  152.         Player reversePlayer = new Player(0,"");
  153.         Player temp = p.next;
  154.         Player next = null;
  155.         while (temp != null){
  156.             next = temp.next;
  157.             temp.next = reversePlayer.next;
  158.             reversePlayer.next =temp;
  159.             temp = next;
  160.         }
  161.         p.next = reversePlayer. next;
  162.     }
  164.     //从尾到头打印链表
  165.     public void reversePrint(Player p){
  166.         if (p.next==null || p.next.next==null){
  167.             System.out.println("链表为空");
  168.             return;
  169.         }
  170.         Player temp = p.next;
  171.         Stack<Player> stack = new Stack<>();
  172.         while (temp != null){
  173.             stack.push(temp);
  174.             temp = temp.next;
  175.         }
  176.         while (stack.size()>0){
  177.             System.out.println(stack.pop());
  178.         }
  179.     }
  181.     //方法一：合并两个有序的单链表（缺陷：使用的addByNo方法，所以相同编号的节点会被删掉一个）
  182.     public SingleLinkedList merge(SingleLinkedList sll1,SingleLinkedList sll2){
  183.         //判断链表是否为空
  184.         if (sll1==null){
  185.             System.out.println(sll2);
  186.             return null;
  187.         }
  188.         if (sll2==null){
  189.             System.out.println(sll1);
  190.             return null;
  191.         }
  192.         if (sll1==null&&sll2==null){
  193.             System.out.println("两个链表都为空");
  194.             return null;
  195.         }
  196.         //获取sll2的头结点
  197.         Player p = sll2.getP();
  198.         Player temp =p.next;
  199.         //定义一个集合，用来存取遍历出来sll2的节点
  200.         HashSet<Player> set = new HashSet<>();
  201.         //获取sll2的节点的个数
  202.         int length = sll2.getLength(p);
  203.         //遍历sll2链表，并将其存到集合中
  204.         for (int i = 0; i < length; i++) {
  205.             set.add(temp);
  206.             temp =temp.next;
  207.         }
  208.         //遍历集合，将其添加的sll1中
  209.         for (Player player : set) {
  210.             sll1.addByNo(player);
  211.         }
  212.         return sll1;
  213.     }
  215.     //方法二：合并两个有序的单链表(遍历两个链表的每个节点，判断节点编号的大小，进行排序，最后将剩余一个不是空的链表插入到最后面)
  216.     public SingleLinkedList merge2(SingleLinkedList sll1,SingleLinkedList sll2){
  217.         //创建一个新链表
  218.         SingleLinkedList sll3 = new SingleLinkedList();
  219.         Player p = sll3.getP();//获取新链表的头结点
  220.         Player temp = p;//定义一个辅助头结点
  221.         //获sll1的头结点
  222.         Player p1 = sll1.getP();
  223.         Player temp1 = p1.next;
  224.         //获sll2的头结点
  225.         Player p2 = sll2.getP();
  226.         Player temp2 = p2.next;
  227.         while (temp1!=null&&temp2!=null){
  228.             if(temp1.no>temp2.no){
  229.                 temp.next=temp2;
  230.                 temp2 = temp2.next;
  231.             }else {
  232.                 temp.next=temp1;
  233.                 temp1 = temp1.next;
  234.             }
  235.             temp = temp.next;
  236.         }
  237.         temp.next = temp1!=null?temp1:temp2;
  238.         return sll3;
  239.     }
  241.     //显示整个链表
  242.     public void show(){
  244.         //判断链表是否为空
  245.         if(p.next==null){
  246.             System.out.println("链表为空");
  247.             return;
  248.         }
  249.         //定义一个辅助头结点
  250.         Player temp = p.next;
  251.         //遍历链表
  252.         while (temp!=null){
  253.             System.out.println(temp);
  254.             temp = temp.next;
  255.         }
  256.     }
  257. }

SingleLinkedListDemo测试类

package com.study.linkedlist;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByNo(new Player(11,"欧文"));
        singleLinkedList.addByNo(new Player(23,"詹姆斯"));
        singleLinkedList.addByNo(new Player(34,"安特托昆博"));
        singleLinkedList.addByNo(new Player(30,"库里"));
        singleLinkedList.addByNo(new Player(24,"科比"));

        int l = singleLinkedList.getLength(singleLinkedList.getP());
        System.out.println("有效的头结点个数为："+l);
        singleLinkedList.reversePrint(singleLinkedList.getP());
        singleLinkedList.reverse(singleLinkedList.getP());
        singleLinkedList.getByNo(singleLinkedList.getP(),6);
        singleLinkedList.show();
    }

}

部分方法测试结果

图片.png

2、总结

2.1、增加一个节点（增加到链表的最后）

//添加节点到链表中
    //不考虑编号顺序
    //1.找到当前链表的最后一个节点
    //2.将最后节点的next指向新的节点
    public void add(Player player){

        //定义一个零时的头结点
        Player temp = p;
        //遍历链表，找到最后一个节点
        while (true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next=player;
    }

2.2、按顺序增加一个节点

//添加方法二：按顺序添加，并且添加编号相同的数据时提示添加错误
    public void addByNo(Player player){

        //定义一个零时的头结点
        Player temp = p;
        boolean flag = false;//定义一个标识，判断链表中是否已经存在相同的编号
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no > player.no){
                break;
            }else if (temp.next.no == player.no){
                flag = true;//说明编号存在；
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("球员已经存在，不能加入"+temp.next.no+temp.next.name);
        }else {
            player.next = temp.next;
            temp.next = player;
        }
    }

2.3、修改一个节点

//根据编号修改球员信息
    public void updateByNo(Player player){

        //判断链表是否为空
        if (p.next==null){
            System.out.println("链表为空");
            return;
        }
        Player temp = p.next;
        boolean flag = false;
        while (true){
            if(temp.next==null){
                break;
            }
            if(temp.no==player.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.name= player.name;
        }else {
            System.out.println("没有找到改球员");
        }
    }

2.4、删除一个节点

//根据编号删除节点
    public void deleteByNo(int no){
        //判断链表是否为空
        if (p.next==null){
            System.out.println("链表为空");
            return;
        }
        Player temp = p.next;
        boolean flag = false;
        while (true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no==no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.println("没有找到改球员");
        }
    }

2.5、获取节点有效个数

//获取链节点的有效个数
    public int getLength(Player p){
        if (p.next==null){
            System.out.println("链表为空");
            return 0;
        }
        int length = 0;
        Player temp = p.next;
        while (temp!=null){
            length++;
            temp = temp.next;
        }
        return length;
    }

2.6、查找链表中倒数第K个节点（重点，leetcode原题）

在已知链表的长度下：

//查找单链表中倒数第k个节点
    public void getByNo(Player p,int no){
        if (p.next==null){
            System.out.println("链表为空");
            return;
        }
        int l = getLength(p);
        if (no<0 || no >l){
            System.out.println("没有该节点");
            return;
        }
        Player temp = p.next;
        for (int i = 0; i < l - no; i++) {
            temp = temp.next;
        }
        System.out.println("倒数第"+no+"个节点的数据为："+temp.no+temp.name);
    }

链表的长度未知，可采用双指针来查找：

//核心代码
ListNode first = head,last = head;
for(int i=0;i<k;i++){
    if(first==null){
        return null;
    }
    first = first.next;
}
while(first!=null){
    first = first.next;
    last = last.next;
}
return last;

2.7、翻转链表（重点，LeetCode原题）

//翻转链表
public void reverse(Player p){
    if (p.next==null || p.next.next==null){
        System.out.println("链表为空");
        return;
    }
    Player reversePlayer = new Player(0,"");
    Player temp = p.next;
    Player next = null;
    while (temp != null){
        next = temp.next;
        temp.next = reversePlayer.next;
        reversePlayer.next =temp;
        temp = next;
    }
    p.next = reversePlayer. next;
}

2.8、从尾到头打印链表（重点，LeetCode原题）

//从尾到头打印链表
//采用栈的特点
public void reversePrint(Player p){
    if (p.next==null || p.next.next==null){
        System.out.println("链表为空");
        return;
    }
    Player temp = p.next;
    Stack<Player> stack = new Stack<>();
    while (temp != null){
        stack.push(temp);
        temp = temp.next;
    }
    while (stack.size()>0){
        System.out.println(stack.pop());
    }
}

2.9、合并两个有序的链表（重点，leetcode原题）

public SingleLinkedList merge2(SingleLinkedList sll1,SingleLinkedList sll2){
    //创建一个新链表
    SingleLinkedList sll3 = new SingleLinkedList();
    Player p = sll3.getP();//获取新链表的头结点
    Player temp = p;//定义一个辅助头结点
    //获sll1的头结点
    Player p1 = sll1.getP();
    Player temp1 = p1.next;
    //获sll2的头结点
    Player p2 = sll2.getP();
    Player temp2 = p2.next;
    while (temp1!=null&&temp2!=null){
        if(temp1.no>temp2.no){
            temp.next=temp2;
            temp2 = temp2.next;
        }else {
            temp.next=temp1;
            temp1 = temp1.next;
        }
        temp = temp.next;
    }
    temp.next = temp1!=null?temp1:temp2;
    return sll3;
}