链表的表示
链表的表示
由于链表的特点（查询或删除元素都要从头结点开始）,所以我们只要在链表中定义头结点即可,另外如果要频繁用到链表的长度，还可以额外定义一个变量来表示。
需要注意的是这个头结点的定义是有讲究的，一般来说头结点有两种定义形式，一种是直接以某个元素结点为头结点,如下
一种是以一个虚拟的节点作为头结点，即我们常说的哨兵，如下
定义这个哨兵有啥好处呢，假设我们不定义这个哨兵，来看看链表及添加元素的基本操作怎么定义的
/**
* 链表中的结点，data代表节点的值，next是指向下一个节点的引用
*/
class Node {
int data;// 结点的数组域，值
Node next = null;// 节点的引用，指向下一个节点
public Node(int data) {
this.data = data;
}
}
/**
* 链表
*/
public class LinkedList {
int length = 0; // 链表长度，非必须，可不加
Node head = null; // 头结点
public void addNode(int val) {
if (head == null) {
head = new Node(val);
} else {
Node tmp = head;
while (tmp.next != null) {
tmp.next = tmp;
}
tmp.next = new Node(val);
}
}
}发现问题了吗，注意看下面代码
有两个问题：
1.每插入一个元素都要对头结点进行判空比较，如果一个链表有很多元素需要插入，就需要进行很多次的判空处理，不是那么高效
2.头结点与其他结点插入逻辑不统一（一个需要判空后再插入，一个不需要判空直接插入）,从程序逻辑性来说不是那么合理（因为结点与结点是平级，添加逻辑理应相同）
如果定义了哨兵结点，以上两个问题都可解决，来看下使用哨兵结点的链表定义
public class LinkedList {
int length = 0; // 链表长度，非必须，可不加
Node head = new Node(0); // 哨兵结点
public void addNode(int val) {
Node tmp = head;
while (tmp.next != null) {
tmp.next = tmp;
}
tmp.next = new Node(val);
}
}可以看到，定义了哨兵结点的链表逻辑上清楚了很多,不用每次插入元素都对头结点进行判空，也统一了每一个结点的添加逻辑。
所以之后的习题讲解中我们使用的链表都是使用定义了哨兵结点的形式。
做了这么多前期的准备工作，终于要开始我们的正餐了：链表解题常用套路–翻转！
链表常见解题套路
热身赛
既然我们要用链表解题，那我们首先就构造一个链表吧
题目：给定数组 1，2，3，4 构造如下链表 head–>4—->3—->2—->1
看清楚了，是逆序构造链表！顺序构造我们都知道怎么构造，对每个元素持续调用上文代码定义的 addNode 方法即可（即尾插法），与尾插法对应的，是头插法，即把每一个元素插到头节点后面即可，这样就能做到逆序构造链表，如图示（以插入1，2 为例）
头插法比较简单，直接上代码,直接按上图的步骤来完成逻辑，如下
public class LinkedList {
int length = 0; // 链表长度，非必须，可不加
Node head = new Node(0); // 哨兵节点
// 头插法
public void headInsert(int val) {
// 1.构造新结点
Node newNode = new Node(val);
// 2.新结点指向头结点之后的结点
newNode.next = head.next;
// 3.头结点指向新结点
head.next = newNode;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
int[] arr = {1,2,3,4};
// 头插法构造链表
for (int i = 0; i < arr.length; i++) {
linkedList.headInsert(arr[i]);
}
// 打印链表,将打印 4-->3-->2-->1
linkedList.printList();
}
}小试牛刀
现在我们加大一下难度，来看下曾经的 Google 面试题：给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 内删除这个节点。
如图示：给定值为 2 的结点，如何把这个结点给删了。
我们知道，如果给定一个结点要删除它的后继结点是很简单的，只要把这个结点的指针指向后继结点的后继结点即可
如图示：给定结点 2，删除它的后继结点 3， 把结点 2 的 next 指针指向 3 的后继结点 4 即可。
但给定结点 2，该怎么删除结点 2 本身呢，注意题目没有规定说不能改变结点中的值，所以有一种很巧妙的方法，狸猫换太子！我们先通过结点 2 找到结点 3，再把节点 3 的值赋给结点 2，此时结点 2 的值变成了 3，这时候问题就转化成了上图这种比较简单的需求，即根据结点 2 把结点 3 移除即可，看图
不过需要注意的是这种解题技巧只适用于被删除的指定结点是中间结点的情况，如果指定结点是尾结点，还是要老老实实地找到尾结点的前继结点，再把尾结点删除，代码如下
/**
* 删除指定的结点
* @param deletedNode
*/
public void removeSelectedNode(Node deletedNode) {
// 如果此结点是尾结点我们还是要从头遍历到尾结点的前继结点，再将尾结点删除
if (deletedNode.next == null) {
Node tmp = head;
while (tmp.next != deletedNode) {
tmp = tmp.next;
}
// 找到尾结点的前继结点，把尾结点删除
tmp.next = null;
} else {
Node nextNode = deletedNode.next;
// 将删除结点的后继结点的值赋给被删除结点
deletedNode.data = nextNode.data;
// 将 nextNode 结点删除
deletedNode.next = nextNode.next;
nextNode.next = null;
}
}了解更多算法内容，请持续关注：阿里云开发者社区算法编程官方技术圈 !
来源 | 五分钟学算法
作者 | 程序员小吴
