准备算法面试一定不能忽略基础，算法面试中链表的问题是经常出现的。
链表是一种特殊的线性结构，由于不能像数组一样进行随机的访问，所以和链表相关的问题有他自身的特点。我将之称为穿针引线。我们在这一章，就来看一看，如何在链表中穿针引线。
例1：LeetCode 第 206 题：反转链表
传送门：反转链表。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
分析：分析这道问题的时候写的草稿。
[站外图片上传中...(image-448955-1558822745594)]
题目的要求是节点是不动的，而应该改变的是节点的 next 指针的方向。而不应该是去修改链表的值，使得这个新的链表看起来是反向的。指针变化的过程其实并不复杂，关键是我们把图画出来，需要多少个临时变量，指针变化过程也就一目了然了。我们可以看到，reverseList 的参数是一个 ListNode 类型的对象，即对象的头结点。
Java 代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class Solution {
/**
* 1、结合自己画的图并不难写出逻辑，把图画出来，迭代的思路就已经有了
* 2、借助三个指针：pre、current、next 完成链表的反转
* 3、
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
// 初始化上一个指针
ListNode pre = null;
// 初始化当前指针
ListNode current = head;
while (current != null) {
// 第 1 步：先把 next 存起来，下一轮迭代要用到
ListNode next = current.next;
// 第 2 步：实现当前节点的 next 指针的反转
current.next = pre;
// 第 3 步：重新定义下一轮迭代的循环变量
pre = current;
current = next;
}
// 遍历完成以后，原来的最后一个节点就成为了 pre
// 这个 pre 就是反转以后的新的链表的头指针
return pre;
}
}
看看代码是不是很简单。这个解法的时间复杂度是 ，因为它仅仅遍历了一次链表，空间复杂度是
，因为这里仅仅使用了有限个的“指针”，帮助我们完成了链表的反转操作。
补充：如果不使用“穿针引线”，还可以用递归完成。
练习1：LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转
传送门：英文网址：92. Reverse Linked List II ，中文网址：92. 反转链表 II 。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转-1
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// 创建一个虚拟的结点（dummy）
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
int k = 0;
while (++k < m) {
if (pre != null) {
pre = pre.next;
}
}
// tail 是尾巴的意思
ListNode tail = pre.next;
while (++k <= n) {
ListNode temp = pre.next;
pre.next = tail.next;
tail.next = tail.next.next;
pre.next.next = temp;
}
return dummy.next;
}
}
Java 代码：
public class Solution2 {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < m - 1; i++) {
// pre 指针向后移动
pre = pre.next;
}
// System.out.println(pre.val);
ListNode p = pre.next;
ListNode curNode;
for (int i = 0; i < n - m; i++) {
curNode = p.next;
p.next = curNode.next;
curNode.next = pre.next;
pre.next = curNode;
}
return dummy.next;
}
}
Java 代码：
public ListNode reverseBetween(ListNode head, int m, int n) {
// 设置 dummyNode 是这一类问题的一般做法
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next;
for (int i = 0; i < n - m; i++) {
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode.next;
}
另一种解法：来自“小吴”的动图，比较自然，但是代码写起来不够简洁。
图示：
LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转-2
Python 代码：
LeetCode 第 92 题：反转从位置 m 到 n 的链表，k 个组进行一次反转-3
（本节完）
网友评论