剑指offer面试题16 反转链表
考察点
链表
知识点
三指针遍历链表
题目
分析
关于链表的考点其实就是一个遍历问题，要么是双指针遍历，要么是三指针遍历，而三指针遍历往往是最前面的指针初始化为空，中间指针初始化为头结点，第三个指针初始化为头结点的next结点。类似这种题目我们往往需要通过归纳法的手段找出规律：假设链表a->b->c，现在要想改成a<-b，是不是需要先把c结点存起来，否则b到c的链路就断掉了，因为我们可以针对链表中每个结点重复此过程，直到尾结点，这里一定要注意尾结点的处理方式，找到尾结点以后需要把它变成头结点。
public class LinkNode {int val;LinkNode next;public LinkNode(int data) {this.val = data;this.next = null;}
}
public class LinkList {LinkNode head;public LinkList() {this.head = null;}public void reverseLink() {LinkNode pre = null;LinkNode cur = this.head;while (cur != null) {LinkNode next = cur.next;if (next == null) {this.head = cur;}cur.next = pre;pre = cur;cur = next;}}//添加元素public void addNode(int data) {LinkNode node = new LinkNode(data);if (this.head == null) {this.head = node;} else {LinkNode cur = this.head;while(cur.next != null) {cur = cur.next;}cur.next = node;}}//正序打印public void print() {LinkNode node = this.head;while(node != null) {System.out.print(node.val);System.out.print(" ");node = node.next;}System.out.println();}
}
public class Sixteen {public static void main(String[] args) {LinkList linklist = new LinkList();linklist.addNode(1);linklist.addNode(2);linklist.addNode(3);linklist.addNode(4);linklist.addNode(5);linklist.print();linklist.reverseLink();linklist.print();linklist = new LinkList();linklist.reverseLink();linklist.print();}
}