链表（下）：如何轻松写出正确的链表代码
2019-01-01 本文已影响4人
Rreply
技巧一：理解指针或者引用的意义
指针或者引用都是存储对象的内存地址。
将某个变量赋值给指针，就是将这个变量的地址赋值给指针，或者反过来说指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能够找到这个变量
以下面这句代码为例：
p ->next = q
p ->next就是一个指针，把q的内存地址赋值给它。
技巧二：警惕指针丢失和内存泄漏
插入节点
如图所示。
正确的代码应该是
b = a.next;
a.next = x;
x.next = b;
但是有时候写成如下代码的时候就会发生指针丢失：
a.next = x;
x.next = a.next;
技巧三：利用哨兵简化实现难度
一般我们插入和删除一个节点是通过如下代码来实现的：
//在a、b节点之间插入c节点
b = a.next;
a.next = c;
c.next = b;
//删除a之后的b节点
a.next = a.next.next;
但是上述代码对于空链表来说并不适用，因为空链表不存在a.next。这种情况下，我们就需要特殊处理：
//在空链表中插入节点a
if(head == null){
head = a;
}
//在只有头结点的链表中删除节点
if(head.next == null){
head = null;
}
针对链表的插入和删除操作，需要对第一个节点和删除最后一个节点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁。
这个时候就需要哨兵来帮助解决了。
我们观察上面针对非空链表实现的代码：
- 插入节点时，因为空链表不存在
head，所以head.next会造成空指针异常。 - 删除节点的时候，
head.next.next会造成空指针异常。
所以我们针对这个情况，在头指针之前加一个哨兵指针，哨兵指针没有存储的数据，它指向头结点，它的功能就是在空链表插入或者只有一个节点删除时作为头结点来使用。这样不管什么情况下，链表都不是空链表了。此时拥有哨兵的链表叫做带头链表。
带头链表
技巧四：重点留意边界条件处理
我们在写好一个链表之后应该考虑下面四种情况：
- 如果链表为空，链表是否能够正常工作。
- 如果链表只有一个节点，能够正常工作。
- 如果链表只有两个节点，能够正常工作。
- 在处理头结点和尾节点的时候，能够正常工作。
如果我们的代码在上述四种情况下都能够正常运行，说明一般是没有问题的。
技巧五：使用举例和画图方法
有些特殊情况，如果仅仅是凭着脑内思考，可能不会想的很清楚。这个时候可以把这些情况分别列举出来，然后通过图示展示出来，更有利于逻辑的理顺。
举例画图
技巧六：多写多练
把下面几种链表操作都手动实现一边就不怕了。
- 链表反转
- 环的检测
- 两个有序的链表的合并
- 删除链表倒数第n个节点
- 求链表的中间节点
1. 链表反转
import java.util.ArrayList;
public class Reverse {
/**
* 第一种方法，通过将链表中的节点存到数组中，然后从后往前读取.
*
* @param listNode 头结点
* @return false即为失败，true成功
*/
boolean reverse1(ListNode listNode) {
ListNode initial = listNode;
//新建一个数组
ArrayList<ListNode> arrayNodes = new ArrayList<>();
if (listNode == null || listNode.next == null) {
return true;
}
while (listNode.next != null) {
arrayNodes.add(listNode);
listNode = listNode.next;
}
for (int i = 0; i < arrayNodes.size(); i++) {
initial.val = arrayNodes.get(i).val;
initial = initial.next;
}
return true;
}
/**
* 第二种方法，采用递归的思想来解决
*
* @param listNode 头节点
* @return 返回已经反转的节点
*/
ListNode reverse2(ListNode listNode) {
if (listNode == null || listNode.next == null) {
return listNode;
}
ListNode nextCode = listNode.next;
nextCode = reverse2(nextCode);
nextCode.next = listNode;
listNode.next = null;
return listNode;
}
/**
* 普通的非递归的方法来解决
*
* @param node the node
* @return false即为失败，true成功
*/
boolean reverse3(ListNode node) {
if (node == null || node.next == null) {
return true;
}
ListNode pre = null;
while (node.next != null) {
ListNode next = node.next;
node.next = pre;
node = next;
pre = node;
}
//最后一个节点反转
node.next = pre;
return true;
}
}
2. 环的检测
import java.util.HashSet;
public class Cycle {
/**
* HasCycle boolean.
* 使用快慢两个节点进行处理，如果快节点能够追上慢节点，说明有环
* 时间复杂度O(n)
* 空间复杂度O(1)
*
* @param head the head
* @return the boolean
*/
public boolean hasCycle1(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//fast.next != null 是为了避免出现空指针异常
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
/**
* Has Cycle 2 boolean.
* 使用一个Set来存储每个节点的内存地址，遍历链表，如果Set中不存在该节点，添加，存在，有环。
* 当遍历遇到null时，说明不为环。
* 空间复杂度：O(n)
* 时间复杂度：O(n)
* @param head the head
* @return the boolean
*/
public boolean hasCycle2(ListNode head) {
HashSet<ListNode> listNodes = new HashSet<>();
while (head != null) {
if (!listNodes.contains(head)) {
listNodes.add(head);
head = head.next;
} else {
return true;
}
}
return false;
}
}
3. 合并两个有序的链表
public class merge {
/**
* Merge list boolean.
* 使用遍历某一链表的方法来进行合并，合并的操作在某一固定的链表上进行，真的是落入了下乘。
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*
* @param a the a
* @param b the b
* @return the boolean
*/
public boolean mergeList(Node a, Node b) {
if (a == null || b == null) {
return false;
}
Node pre = new Node(0);
while (a.next != null && b != null) {
if (a.val > b.val) {
Node temp = b;
b = b.next;
pre.next = temp;
temp.next = a;
} else {
pre = a;
a = a.next;
}
}
//此时a链表已经到头，只需要接上剩余的b链表即可。
if (a.next == null){
a.next = b;
return true;
}
//此时b == null，说明已经完成合并了
return true;
}
/**
* Merge list 2 boolean.
* LeetCode上一位大佬写的，应该是我目前见过的最好的解法了。
* 其思路并没有像我局限在一定要在某一个链表上进行处理。
* 其把两个链表打散，当成分割的节点进行处理。
* 真的是难以望其项背。
* @param a the a
* @param b the b
* @return the boolean
*/
public Node mergeList2(Node a, Node b){
if (a == null){
return b;
}
if (b == null){
return a;
}
//因为链表是从小到大排序的，所以我们必须获取两个链表中最小的下一个节点
if (a.val > b.val){
//当a节点的值比b节点的值大的时候，b节点的next节点还未确定，
// 需要a和b的next节点进行比较，取其中较小的节点
b.next = mergeList2(a, b.next);
return b;
} else {
a.next = mergeList2(a.next, b);
return a;
}
}
}
class Node {
int val;
Node next;
Node(int num) {
val = num;
}
}
5. 删除链表倒数第n个节点
public class Reciprocal {
/**
* 使用快慢两个节点，快节点先比慢节点多走n步。
* 注意：因为这是要删除倒数第n个节点，如果是返回第n个节点，那么就是多走n-1步了。
*
* @param head the head
* @param n the n
* @return 链表删除节点后的head节点
*/
public ListNode getReciprocalN(ListNode head, int n) {
//使用哨兵节点来处理空节点或者节点只有一个的情况
ListNode dummy = new ListNode("start");
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for (int i = 1; i < n+1; i++) {
fast = fast.next;
if (fast == null){
System.out.println("该链表并没有比n更多的节点，删除失败");
return null;
}
}
while (fast != null){
fast = fast.next;
slow = slow.next;
}
//当fast节点到达末尾的时候，slow节点在倒数第n个节点之前的一个节点
slow.next = slow.next.next;
return dummy.next;
}
}
6. 求链表的中间节点
/**
* Definition for singly-linked list.
* 简单地使用快慢速节点处理即可
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
if(fast == null){
return slow;
}
return slow.next;
}
}
