xwzz.jpg
重温：数据结构与算法 - 开篇
重温：数据结构与算法 - 复杂度分析(一)
重温：数据结构与算法 - 复杂度分析(二)
重温：数据结构与算法 - 数组
重温：数据结构与算法 - 链表(一)
前章，介绍了常见的链表数据结构有：
- 单向链表
- 循环链表
- 双向链表
- 双向循环链表
本章主要做几道练习题来加深对链表数据结构印象，每题都需考虑以下边界问题：
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
练习1：单向链表反转
反转前.png
如何将已知的单向链表反转？
反转后.png
思路：遍历所有结点，将当前结点的next指针指向前结点，操作完成后原尾结点作为首结点即可。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
public static Node reverseNode(Node first) {
if (first == null) return null;
if (first.next == null) return first;
// 从首结点开始，首结点的上结点为空结点
Node curNode = first;
Node preNode = null;
while (curNode != null) {
Node tempNext = curNode.next; // 暂存当前结点的下一结点
curNode.next = preNode; // 让当前结点指向上一结点
// 切换到下一结点
preNode = curNode;
curNode = tempNext;
}
return preNode; //循环结束，上一结点就是首结点
}
测试：
// 测试数据
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
// 测试代码
printAll(node1);
Node result = reverseNode(node1);
printAll(result);
输出：
1 2 3 4 5 // 反转前
5 4 3 2 1 // 反转后
练习2：循环链表检测
给你一个任意链表结点，如何校验其是否是循环链表？
思路： 通过快、慢指针同时遍历链表，快指针步长为2，慢指针步长为1，当快指针追上慢指针就是循环链表，否则快指针遍历到尾结点（next->null）就非循环链表。
时间复杂度：O(n)
空间复杂度：O(1)
/**
* 检测链表是否是循环链表
* */
public static boolean checkCircleNode(Node first) {
if (first == null) return false;
Node fast = first.next;
Node slow = first;
while (fast != null && fast.next != null) {
if (fast == slow) return true;
fast = fast.next.next; // 快指针走两步
slow = slow.next; // 慢指针走一步
}
return false;
}
测试：
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
node1.next = node2;
node2.next = node3;
node3.next = node1;
System.out.println(checkCircleNode(node1));
Node node4 = new Node(4);
Node node5 = new Node(5);
node4.next = node5;
node5.next = null;
System.out.println(checkCircleNode(node4));
Node node6 = new Node(6);
System.out.println(checkCircleNode(node6));
Node node7 = new Node(7);
node7.next = node7;
System.out.println(checkCircle(node7));
System.out.println(checkCircleNode(null));
输出：
true
false
false
true
false
练习3：合并有序链表
如何将两个从小到大的有序链表合并为一个有序链表？例如：
- 链表1 : [ 1 , 3 , 5 , 7 , 9 ]
- 链表2 : [ 2 , 4 , 6 , 8 , 10]
- 合并后链表：[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]
思路：
1、比较两者首结点、以最小结点作为合并链表的首结点
2、定义两个指针p,q，分别指向这两链表首结点，定义一个临时指针temp指向合并链表的首结点
3、同时开始遍历两个链表，如果有一个链表先到达尾部，则停止遍历
4、遍历中，取p、q指针数据的较小者链接到合并链表的尾部
5、遍历结束，temp拼接p链表或者q链表剩余结点（两链表长度可能不等）
6、返回合并链表首结点
时间复杂度：O(n)
空间复杂度：O(1)
public static Node mergeSortedNode(Node list1, Node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
// p,q 指针分别指向 链表1、链表2
Node p = list1;
Node q = list2;
// 确认合并链表的首结点
Node head;
if (p.data <= q.data) {
head = p;
p = p.next;
} else {
head = q;
q = q.next;
}
//开始遍历排序
Node tempNode = head;
while (p != null && q != null) {
// 取小值链接到合并链表尾部
if (p.data <= q.data) {
tempNode.next = p;
p = p.next;
} else {
tempNode.next = q;
q = q.next;
}
// 开启下一轮
tempNode = tempNode.next;
}
// 拼接剩余尾部
if (p == null) {
tempNode.next = q;
} else {
tempNode.next = p;
}
return head;
}
测试：
// 测试数据1
public static Node getNodeList1() {
Node node1 = new Node(1);
Node node2 = new Node(3);
Node node3 = new Node(5);
Node node4 = new Node(7);
Node node5 = new Node(9);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
return node1;
}
// 测试数据2
public static Node getNodeList2() {
Node node1 = new Node(2);
Node node2 = new Node(4);
Node node3 = new Node(6);
Node node4 = new Node(8);
Node node5 = new Node(10);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
return node1;
}
// 测试代码
private static void test() {
Node list1 = getNodeList1();
list1.print();
Node list2 = getNodeList2();
list2.print();
Node mergeNode = mergeSortedNode(list1, list2);
mergeNode.print();
}
输出：
1 3 5 7 9
2 4 6 8 10
1 2 3 4 5 6 7 8 9 10
练习4：删除链表的倒数第 n 个结点
思路：如何定位到倒数第n结点？
1、定义快指针，指向正数第n结点；
2、再定义慢指针指向首结点；
3、快慢指针同时以步长1开始遍历链表，当快指针到达尾结点时，慢指针正好停留在倒数第n结点；
4、考虑到单链表删除，需要知道前结点，所以在第3步遍历前定义pre指针指向慢指针的前结点；
5、当遍历完成可能出现两种情况：
- 情况1：pre指向结点不为null，删除慢指针结点即可；
- 情况2：pre指向null，此时要删除的正好是首结点。
时间复杂度：O(n)
空间复杂度：O(1)
public static Node deleteLastTh(Node list, int n) {
if (list == null || n < 1) return list;
Node fast = list;
int i = 1;
while (fast != null && i < n) {
fast = fast.next;
i++;
}
//不存在倒数第n个结点
if (fast == null) return list;
//开始运算，定位倒数n结点
Node slow = list;
Node pre = null;
while (fast.next != null) {
fast = fast.next;
pre = slow;
slow = slow.next;
}
if (pre == null) {
//倒数n结点正好是首结点
list = list.next;
} else {
//循环结束，slow就为倒数第n个结点，操作pre结点删除slow结点
pre.next = pre.next.next;
}
return list;
}
测试：
//测试数据
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
//测试代码
node1.print();
Node node = deleteLastTh(node1, 3);
node.print();
输出：
1 2 3 4 5
1 2 4 5
练习5：求链表的中间结点
思路：
1、定义快慢指针同时遍历链表，快指针步长为2，慢指针步长为1
2、当快指针到达尾结点，慢指针正好在中心结点
时间复杂度：O(n)
空间复杂度：O(1)
public static Node findMiddleNode(Node list) {
if (list == null) return null;
Node slow = list;
Node fast = list;
while (fast.next != null && fast.next.next != null) {
slow = slow.next; // 步长1：慢指针
fast = fast.next.next; // 步长2：快指针
}
return slow;
}
测试：
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
node1.print();
Node middleNode = findMiddleNode(node1);
System.out.println(middleNode.data);
输出：
1 2 3 4 5
3
