【Java数据结构】带头节点单链表的反转，从尾到头输出，输出倒数第k个节点

 1 import java.util.Stack;
 2 
 3 /**
 4  * @author ZhiYi Li
 5  * @create 2020/8/25 20:45
 6  */
 7 public class SingleLinkedTest {
 8     //问题1：查找单链表中倒数第k个节点
 9     //普通思路，先计算链表长度，然后用长度减去k得到顺序数的位置
10     //更装逼的思路，快慢指针思路，定义一个rear=1，定义一个front为k
11     //，先让front先走k个单位，之后front和rear同步增加，当front走到尾部时，rear就是在倒数k个的位置上
12     public static HeroNode getReciprocalK(HeroNode head,int k){
13         if(head.next == null){
14             return null;
15         }
16         HeroNode front = head;
17         HeroNode rear = head;
18         int i;
19         for (i = 0; i < k&&front!=null; i++) {
20             front = front.next;
21         }
22         if(i<k){
23             return null;
24         }
25         while (front!=null){
26             front = front.next;
27             rear = rear.next;
28         }
29         return rear;
30     }
31     //问题二：反转单链表（头插法）
32     public static void reverseNode(HeroNode head){
33         if(head.next == null||head.next.next==null){
34             return;
35         }
36         HeroNode temp = new HeroNode(0,"");//新头节点
37         HeroNode temp2 = head.next;
38         HeroNode temp3;
39         while (temp2!=null){
40             temp3 = temp2.next;
41             temp2.next = temp.next;
42             temp.next = temp2;
43             temp2 = temp3;
44         }
45         head.next = temp.next;
46     }
47     //问题三：从尾到头打印单链表
48     public static void printRearToFront(HeroNode head){
49         //方式一：递归输出,无法不让头节点输出，递归性能差，不建议使用
50         //其实也能让头节点不输出，将以下代码重写一个方法，将head.next传入
51 //        HeroNode temp = head;
52 //        if(temp!=null){
53 //            printRearToFront(temp.next);
54 //            System.out.println(temp);
55 //        }
56         //方式二：使用栈Stack,利用栈的特性来写
57         if(head.next == null){
58             return;
59         }
60         Stack<HeroNode> stack = new Stack<>();
61         HeroNode temp = head.next;
62         while (temp!=null){
63             stack.add(temp);
64             temp=temp.next;
65         }
66         while (stack.size()>0){
67             System.out.println(stack.pop());
68         }
69     }
70     public static void main(String[] args) {
71         SingleLinkedList linkedList = new SingleLinkedList();
72         linkedList.addNodeByNo2(new HeroNode(0,"张三"));
73         linkedList.addNodeByNo2(new HeroNode(1,"李四"));
74         linkedList.addNodeByNo2(new HeroNode(4,"王五"));
75         linkedList.addNodeByNo2(new HeroNode(2,"赵六"));
76         linkedList.addNodeByNo2(new HeroNode(3,"吴七"));
77         linkedList.show();
78         System.out.println("倒数第k个节点：");
79         System.out.println(getReciprocalK(linkedList.getHead(),5));
80         linkedList.show();
81         System.out.println("反转单链表：");
82         reverseNode(linkedList.getHead());
83         linkedList.show();
84         System.out.println("从后往前打印单链表");
85         printRearToFront(linkedList.getHead());
86     }
87 
88 }