java数据结构 - 单链表（腾讯面试题实现单链表反转）

直接上实现代码

//单链表的反转 public static void reverseList(HeroNode head){ //如果当前链表为空，或只有一个节点，无需反转 if (head.next == null || head.next.next == null){ return ; } //定义一个辅助变量，帮助我们遍历 HeroNode cur = head.next; HeroNode next = null;//指向当前节点[cur]的下一个节点 HeroNode reverseHead = new HeroNode(0,"",""); //遍历原来的链表，每遍历一个节点，就将其取出，并放到reverseHead while(cur != null){ next = cur.next;//先保存当前节点的下一个节点 cur.next = reverseHead.next; reverseHead.next = cur;//cur的下一个节点指向新的链表的最前端 cur = next; //把记录的cur.next赋给cur } //将head.next 指向 reverseHead.next，实现单链表反转 head.next = reverseHead.next; }

最主要的是while循环里的逻辑

while(cur != null){ next = cur.next;//先保存当前节点的下一个节点 cur.next = reverseHead.next; reverseHead.next = cur;//cur的下一个节点指向新的链表的最前端 cur = next; //把记录的cur.next赋给cur }

这里一定要画图来慢慢理解，首先一个图是原链表，另一个是新链表的头部，边画图变理解着写逻辑

第一步先保留一下原链表的第二个位置head.next.next也就是代码里的cur.next，如果不保留的话取出来后原链表就断掉了

第二步，让取出来的cur的右边先next指向reverseHead.next

左边是reverseHead.next = cur

然后把next赋给cur

在循环完链表后把链表的头部更换

head.next = reverseHead.next;

下面是完整代码（如果只看反转可以找到reverseList()方法）

package DataStructures.LinkedList; public class SingleLinedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); HeroNode hero4 = new HeroNode(4, "林冲", "豹子头"); //创建要给的链表 SingleLinkedList linkedList = new SingleLinkedList(); //加入(按照加入的顺序) // linkedList.add(hero1); // linkedList.add(hero2); // linkedList.add(hero3); // linkedList.add(hero4); //加入（按照no序号排序） linkedList.addByOrder(hero1); linkedList.addByOrder(hero4); linkedList.addByOrder(hero2); linkedList.addByOrder(hero3); linkedList.addByOrder(hero3); // //显示(修改前) // System.out.println("显示(修改前)"); // linkedList.list(); // //测试修改节点的代码 // HeroNode hero5 = new HeroNode(2, "chun", "chunchun"); // linkedList.updata(hero5); // //显示(修改后) // System.out.println("显示(修改后)"); // linkedList.list(); // //删除节点 // linkedList.delete(2); // System.out.println("显示删除后"); // linkedList.list(); // // linkedList.delete(2); // System.out.println("显示删除后"); // linkedList.list(); // //测试一下 求单链表中有效节点的个数 // System.out.println("有效的节点个数 = "+getLength(linkedList.getHead())); // // //测试一下看看是否得到倒数第k个节点 // HeroNode heroNode = fidLastIndexNode(linkedList.getHead(), 2); // // System.out.println(heroNode); linkedList.list(); reverseList(linkedList.getHead()); linkedList.list(); } // 1.获取到单链表的节点的个数（如果有头结点，不统计头结点） public static int getLength(HeroNode head){ if (head.next == null){ return 0; } int length = 0; //定义一个辅助变量， HeroNode cur = head.next; while(cur !=null){ length++; cur = cur.next;//遍历 } return length; } //查找单链表中的倒数第K个节点【新浪面试题】 //思路 // 1.编写一个方法，节后head节点，同时接收一个index // 2.index表示倒数第index个节点 // 3.先把链表从头到尾遍历，得到链表的总长度 // 4.得到size后从链表的第一个开始遍历，遍历size-index个就可以得到 // 如果找到了，则返回该节点，否则返回null public static HeroNode fidLastIndexNode(HeroNode head, int index){ //判断如果为空，则返回null if (head.next == null){ return null; } //第一个遍历得到链表的长度（节点个数） //先做一个index的校验 int size = getLength(head); if (index<=0 || index> size){ return null; } //定义辅助变量 HeroNode temp = head.next; //遍历，for循环定位到倒数的index个 for (int i=0; i<size - index; i++){ temp = temp.next; } return temp; } //单链表的反转 public static void reverseList(HeroNode head){ //如果当前链表为空，或只有一个节点，无需反转 if (head.next == null || head.next.next == null){ return ; } //定义一个辅助变量，帮助我们遍历 HeroNode cur = head.next; HeroNode next = null;//指向当前节点[cur]的下一个节点 HeroNode reverseHead = new HeroNode(0,"",""); //遍历原来的链表，每遍历一个节点，就将其取出，并放到reverseHead while(cur != null){ next = cur.next;//先保存当前节点的下一个节点 cur.next = reverseHead.next; reverseHead.next = cur;//cur的下一个节点指向新的链表的最前端 cur = next; //把记录的cur.next赋给cur } //将head.next 指向 reverseHead.next，实现单链表反转 head.next = reverseHead.next; } } //定义一个SingleLinkedList 管理人物 class SingleLinkedList{ //初始化一个头结点，头结点不要动，不存放具体数据 private HeroNode head = new HeroNode(0,"",""); public HeroNode getHead() { return head; } //添加节点到单链表 //思路：当不考虑编号的顺序时 //1.找到当前链表的最后节点 //2.将最后这个节点的next 指向 新的节点 public void add(HeroNode heroNode){ //因为head节点不能动，因此我们需要一个辅助变量 temp HeroNode temp = head; //遍历链表，找到最后 while(true){ //找到链表的最后 if(temp.next == null){ break; } //如果没找到，temp后移 temp = temp.next; } //当退出while循环时temp指向了链表的最后 //将最后这个节点的next 指向 新的节点 temp.next = heroNode; } //第二种方式在添加人物的时候，根据排名将英雄插入到指定位置 //（如果有这个排名，则添加失败，并给出提示） public void addByOrder(HeroNode heroNode){ //因为头结点不能动，我们仍然需要通过一个辅助变量来帮助找到添加的位置 //因为单链表，因此我们找的temp是位于添加位置的前一个节点，否则插入不了,因为前一个节点next才可以找到新插入的 HeroNode temp = head; boolean flag = false; while (true) { if (temp.next == null) {//说明temp已经在链表最后 break; } if (temp.next.no > heroNode.no) { //位置找到，就在temp后面插入 break; }else if (temp.next.no == heroNode.no){//说明新添加的编号存在 flag = true;//说明编号存在 break; } temp = temp.next; //后移 } //判断flag 的值 if(flag){//不能添加，已经存在 System.out.printf("人物编号%d 已经存在，不能添加\n",heroNode.no); } else { //插入到链表中，temp后 heroNode.next = temp.next; //连接新的节点的next和下一个的data temp.next = heroNode; //连接上一个节点的next和新节点的数据 } } //修改节点信息，根据no来修改，no不能改变 public void updata(HeroNode newHeroNode){ //判断是否为空 if (head.next == null){ System.out.println("链表为空"); return; } //找到需要修改的节点，根据no编号 //定义一个辅助变量 HeroNode temp = head.next; boolean flag = false; while (true){ if (temp == null){ break;//已经遍历完 } if (temp.no == newHeroNode.no){ //找到 flag = true; break; } temp = temp.next; } //判断flag ，是否找到需要修改的 if (flag){ temp.name = newHeroNode.name; temp.nickName = newHeroNode.nickName; }else {//没找到 System.out.printf("没有找到编号：%d 的节点，不能修改",newHeroNode.no); } } //删除节点 //思路： // 1.先找到需要删除的这个节点的前一个节点， // 2.temp.next = temp.next.next // 被删除的节点没有引用指向，会被GC回收 public void delete(int no){ if (head.next == null){ System.out.println("链表为空，不能删除"); return; } //找到需要修改的节点，根据no编号 //定义一个辅助变量 HeroNode temp = head; boolean flag = false;//标记是否找到待删除的节点 while (true){ if (temp.next == null){ //节点遍历完毕 break; } if (temp.next.no == no){//找到节点no flag = true; break; } temp = temp.next; //temp后移 } if (flag){//找到no temp.next = temp.next.next; }else { System.out.printf("链表里没有no为：%d 的节点\n",no); } } //展示链表 public void list(){ //先判断链表是否为空 if (head.next == null){ return; } //因为头结点不能动，因此我们需要一个辅助变量来遍历 HeroNode temp = head.next; while(true){ //判断链表是否为空 if (temp == null){ break; } //输出节点信息 System.out.println(temp); //将temp后移，一定要 temp = temp.next; } } } //定义一个heroNode，每个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; } //为了显示方便重写toString @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }