下面看一个比较经典的问题“两两交换链表中的结点”。
例1：LeetCode 第 24 题：两两交换链表中的结点
传送门：英文网址：24. Swap Nodes in Pairs ，中文网址：24. 两两交换链表中的节点 。
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.说明:
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
分析：两种方法：1、用递归来做就特别简单；2、穿针引线比较麻烦。
解法1：穿针引线做法：设计以下 4 个引用（指针）。
1、成对的结点 1 ：node1
2、成对的结点 2 ：node2
3、成对的结点 1 的前驱：p
4、成对的结点 2 的后继：next
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class Solution {
/**
* 交换链表中成对的元素
* （自己把图画出来，对于指针交换的过程就好理解了）
*
* @param head
* @return
*/
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode p = dummyNode;
while (p.next != null && p.next.next != null) {
ListNode node1 = p.next;
ListNode node2 = node1.next;
ListNode next = node2.next;
node1.next = next;
node2.next = node1;
p.next = node2;
p = node1;
}
return dummyNode.next;
}
public ListNode createLinkedList(int[] arr) {
ListNode head = new ListNode(arr[0]);
ListNode current = head;
for (int i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
public void printLinkedList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.printf("%d => ", current.val);
current = current.next;
}
System.out.println("NULL ");
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
Solution solution = new Solution();
ListNode head1 = solution.createLinkedList(arr);
solution.printLinkedList(head1);
ListNode reverseHead = solution.swapPairs(head1);
solution.printLinkedList(reverseHead);
}
}
说明：以下及其以后的动图如果没有特别说明，都来自这个伟大的 GitHub 仓库：https://github.com/MisterBooo/LeetCodeAnimation/blob/master/Readme.md。
image
解法2：如果使用递归的方法，就特别简单。
Java 代码：
/**
* @author liwei
* @date 18/7/4 下午9:42
*/
public class Solution2 {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p1 = head;
ListNode p2 = head.next;
ListNode newHead = swapPairs(p2.next);
// 下面这两行代码可以交换
p1.next = newHead;
p2.next = p1;
return p2;
}
}
下面这样写就更简单了：
Java 代码：
public class Solution4 {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode first = head;
ListNode second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
public static void main(String[] args) {
// 给定 1->2->3->4, 你应该返回 2->1->4->3.
int[] nums = {1, 2, 3, 4, 5};
ListNode head = new ListNode(nums);
Solution solution = new Solution();
ListNode swapPairs = solution.swapPairs(head);
System.out.println(swapPairs);
}
}
参考资料：https://blog.csdn.net/Koala_Tree/article/details/81476772。
练习
练习1：LeetCode 第 25 题：
传送门：英文网址：25. Reverse Nodes in k-Group ，中文网址：25. k个一组翻转链表 。
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：
1->2->3->4->5当 k = 2 时，应当返回:
2->1->4->3->5当 k = 3 时，应当返回:
3->2->1->4->5说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
// 参考资料：https://blog.csdn.net/weiyongle1996/article/details/78473055
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 使用递归写法的话，先考虑特殊情况
if (head == null || head.next == null || k <= 1) {
return head;
}
// 探测长度的结点
ListNode tempNode = head;
int curK = k;
while (tempNode != null && curK != 0) {
curK--;
tempNode = tempNode.next;
}
// 如果够数了，先考虑反转
if (curK == 0) {
// 下面开始反转
ListNode pre = null;
ListNode curNode = head;
for (int i = 0; i < k; i++) {
ListNode nextNode = curNode.next;
curNode.next = pre;
pre = curNode;
curNode = nextNode;
}
head.next = reverseKGroup(tempNode, k);
return pre;
}
return head;
}
public static void main(String[] args) {
int[] nums = new int[]{1, 2};
ListNode head = new ListNode(nums);
Solution solution = new Solution();
ListNode reverseKGroup = solution.reverseKGroup(head, 2);
System.out.println(reverseKGroup);
}
}
练习2：LeetCode 第 147 题：单链表的插入排序
传送门：英文网址：147. Insertion Sort List ，中文网址：147. 对链表进行插入排序 。
对链表进行插入排序。
image插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3 输出: 1->2->3->4示例 2：
输入: -1->5->3->4->0 输出: -1->0->3->4->5
分析：这道题的题意我们感觉有那么些误导我们的意思，我们能想到从头开始找结点应该插入的位置，但感觉这种做法又不像插入排序。解决这个问题不要太死板，不要怕麻烦我觉得是解这道问题的关键（这句话感觉跟没说一个样，_）。
- 插入排序每次会将遍历到的一个元素插入到已经排序的部分；
- 熟悉插入排序的朋友们都知道，这种插入过程是从后向前的，但是对于单链表来说，只保存了当前结点到下一个结点的 next 指针，并没有保存从当前结点到上一个节点的 pre 指针；
- 我们就要变换思路了，每次都要从链表的第 1 个元素开始，找到新遍历的节点适合插入的位置，进行穿针引线；
- 具体来说对于单链表的第 1 个元素，涉及到头结点的操作的时候，我们的做法往往是设计一个虚拟头结点，以简化编码。
综上所述，想清楚上面的问题，写出正确的代码应该不是难事。
为一个链表实现插入排序。
LeetCode 第 147 题：单链表的插入排序-1
LeetCode 第 147 题：单链表的插入排序-2
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
public class Solution {
public ListNode insertionSortList(ListNode head) {
// 先写最特殊的情况
if (head == null) {
return null;
}
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode curNode = head;
ListNode pre;
ListNode next;
while (true) {
// 如果遍历下去，是顺序排列的话，那最简单了，curNode 指针向前就行了
// 这一步是一个循环的过程
// 暂存当前结点的下一结点
while (curNode.next != null && curNode.val <= curNode.next.val) {
curNode = curNode.next;
}
// 下面针对上一步跳出循环的两个条件进行特殊处理
if (curNode.next == null) {
// 如果后面没有元素了，那就说明，此时链表已经有序，可以结束我们的排序逻辑了
break;
} else {
// 否则就一定满足 curNode.val > curNode.next.val; 为真
// pre 打回到起点
pre = dummyNode;
next = curNode.next;
// 把 pre 挪到可以放置 next 结点的上一个位置
while (pre.next.val < next.val) {
pre = pre.next;
}
// 穿针引线的 3 个步骤，请见图 https://liweiwei1419.github.io/images/leetcode-solution/147-1.jpg
// 穿针引线步骤 1
curNode.next = next.next;
// 穿针引线步骤 2
next.next = pre.next;
// 穿针引线步骤 2
pre.next = next;
}
}
return dummyNode.next;
}
public static void main(String[] args) {
int[] nums = new int[]{3, 7, 9, 10, 8};
ListNode head = new ListNode(nums);
Solution solution = new Solution();
ListNode insertionSortList = solution.insertionSortList(head);
System.out.println(insertionSortList);
}
}
等价写法：
Java 代码：
public class Solution2 {
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return null;
}
// 虚拟头结点
ListNode dummyNode = new ListNode(-1);
ListNode preNode = dummyNode;
// 用于遍历的指针
ListNode curNode = head;
ListNode next = null;
// 没有这一步：dummyNode.next = head;
while (curNode != null) {
next = curNode.next;
// 这一步是找到一个正确的位置插入，只要比 curNode 的值小，都应该跳过
// 直到遇到第 1 个大于等于它的元素
while (preNode.next != null && preNode.next.val < curNode.val) {
preNode = preNode.next;
}
// 应该把 node 放在 pre 的下一个
curNode.next = preNode.next;
preNode.next = curNode;
preNode = dummyNode;
curNode = next;
}
return dummyNode.next;
}
public static void main(String[] args) {
int[] nums = new int[]{3, 7, 9, 10, 8};
ListNode head = new ListNode(nums);
Solution2 solution2 = new Solution2();
ListNode insertionSortList = solution2.insertionSortList(head);
System.out.println(insertionSortList);
}
}
练习3：LeetCode 第 148 题：单链表的排序，使用归并排序
传送门：英文网址：148. Sort List ，中文网址：148. 排序链表 。
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
写一个排序算法，用 的时间复杂度为一个链表进行排序。
对于单链表而言，归并排序是一个不错的选择。
思路1：自顶向下的归并排序。
注意1：特别注意下面这么一段：
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
说明：
- 这个方法走到这里，因为有前面的特判，所以至少得有
个结点，才可以排序。而取中点的操作，只有在“下个结点”和“下下结点”都存在的时候，才能这么做；
- 看看这个循环的循环体就明白了。
注意2：找到中间结点以后，记得把链表“从中切断”，这是符合逻辑的。
Python 代码：
class Solution:
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
# 找到中点
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
head2 = slow.next
slow.next = None
lnode = self.sortList(head)
rnode = self.sortList(head2)
return self.__merge_two_sorted_list(lnode, rnode)
def __merge_two_sorted_list(self, head1, head2):
if head1 is None:
return head2
if head2 is None:
return head1
if head1.val < head2.val:
head1.next = self.__merge_two_sorted_list(head1.next, head2)
return head1
else:
head2.next = self.__merge_two_sorted_list(head1, head2.next)
return head2
另一种写法：
特别注意，如果是
while fast and fast.next:
p = slow
slow = slow.next
fast = fast.next.next
这种取法，==遇到两个结点的时候，slow 会向前走一步，但是截断得在 slow 结点之前，否则会进入死循环，按照我说的，画一个两个截点的链表就很清楚了==。
遇到死循环的时候，不要着急，还有耐心 debug，分析代码运行流程，很多时候问题就迎刃而解了。
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# 这里有个小陷阱，如果遇到问题，不要着急，代码调试就好了
class Solution:
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
# 找到中点
slow = head
fast = head
while fast and fast.next:
p = slow
slow = slow.next
fast = fast.next.next
p.next = None
# print_node_list(head)
# print_node_list(head2)
lnode = self.sortList(head)
rnode = self.sortList(slow)
return self.__merge_two_sorted_list(lnode, rnode)
def __merge_two_sorted_list(self, head1, head2):
if head1 is None:
return head2
if head2 is None:
return head1
if head1.val < head2.val:
head1.next = self.__merge_two_sorted_list(head1.next, head2)
return head1
else:
head2.next = self.__merge_two_sorted_list(head1, head2.next)
return head2
def create_node_list(arr):
head = ListNode(arr[0])
cur = head
for i in range(1, len(arr)):
cur.next = ListNode(arr[i])
cur = cur.next
return head
def print_node_list(head):
while head:
print(head.val, '->', end=' ')
head = head.next
print('NULL')
if __name__ == '__main__':
arr = [4, 2, 1, 3]
head = create_node_list(arr)
print_node_list(head)
solution = Solution()
result = solution.sortList(head)
print_node_list(result)
思路2：自底向上的归并排序。
我以前写了一个示意图，可以点这里看，思想还是很简单的。
（本节完）
