第 2 关 | 两天写了三次的链表反转：2.白银挑战——链表反转的拓展问题-灵析社区
时光小少年1. 指定区间反转
1.1. 头插法
方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)，但遍历了链表 2次，可不可以只遍历一次呢？答案是可以的。我们依然画图进行说明，我们仍然以方法一的序列为例进行说明。
反转的整体思想是，在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。
这个过程就是前面的带虚拟结点的插入操作，每走一步都要考虑各种指针怎么指，既要将结点摘下来接到对应的位置上，还要保证后续结点能够找到，请读者务必画图看一看，想一想到底该怎么调整。代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
for(int i = 0; i< left - 1;i++){
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next;
for(int i = 0; i < right - left;i++){
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode.next;
}
}
def reverseBetween(self, head, left, right) :
# 设置 dummyNode 是这一类问题的一般做法
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
return dummy_node.next
struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
struct ListNode* dummyNode = (struct ListNode*)malloc(sizeof(struct ListNode));
dummyNode->next = head;
struct ListNode* pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
struct ListNode* cur = pre->next;
struct ListNode* next;
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
struct ListNode* newHead = dummyNode->next;
free(dummyNode);
return newHead;
}
1.2. 穿针引线法
这种方式能够复用我们前面讲的链表反转方法，但是实现难度仍然比较高一些。
我们以反转下图中蓝色区域的链表反转为例：
我们可以这么做：先确定好需要反转的部分，也就是下图的 left 到 right 之间，然后再将三段链表拼接起来。这种方式类似裁缝一样，找准位置减下来，再缝回去。这样问题就变成了如何标记下图四个位置，以及如何反转left到right之间的链表。
算法步骤：
●第 1 步：先将待反转的区域反转；
●第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。
编码细节我们直接看下方代码。思路想明白以后，编码不是一件很难的事情。这里要提醒大家的是，链接什么时候切断，什么时候补上去，先后顺序一定要想清楚，如果想不清楚，可以在纸上模拟，思路清晰。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
// 建议写在 for 循环里，语义清晰
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
ListNode rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// 第 3 步：切出一个子链表
ListNode leftNode = pre.next;
ListNode succ = rightNode.next;
// 思考一下，如果这里不设置next为null会怎么样
rightNode.next = null;
// 第 4 步：同第 206 题，反转链表的子区间
reverseLinkedList(leftNode);
// 第 5 步：接回到原来的链表中
//想一下，这里为什么可以用rightNode
pre.next = rightNode;
leftNode.next = succ;
return dummyNode.next;
}
private void reverseLinkedList(ListNode head) {
// 也可以使用递归反转一个链表
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
}
class Solution(object):
# 完成链表反转的辅助方法
def reverse_list(self,head):
# 也可以使用递归反转一个链表
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
def reverseBetween(self, head, left, right) :
# 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
# 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
# 建议写在 for 循环里，语义清晰
for _ in range(left - 1):
pre = pre.next
# 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
right_node = pre
for _ in range(right - left + 1):
right_node = right_node.next
# 第 3 步：切断出一个子链表（截取链表）
left_node = pre.next
curr = right_node.next
# 注意：切断链接
pre.next = None
right_node.next = None
# 第 4 步：同第 206 题，反转链表的子区间
self.reverse_list(left_node)
# 第 5 步：接回到原来的链表中
pre.next = right_node
left_node.next = curr
return dummy_node.next
2. 两两交换链表中的节点
这是一道非常重要的问题，读者务必理解清楚。
LeetCode24.给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
如果要解决该问题，将上面小节的K换成2不就是这个题吗？道理确实如此，但是如果K为2的时候，可以不需要像K个一样需要先遍历找到区间的两端，而是直接取前后两个就行了，因此基于相邻结点的特性重新设计和实现就行，不需要上面这么复杂的操作。
如果原始顺序是 dummy -> node1 -> node2，交换后面两个节点关系要变成 dummy -> node2 -> node1，事实上我们只要多执行一次next就可以拿到后面的元素，也就是类似node2 = temp.next.next这样的操作。
两两交换链表中的节点之后，新的链表的头节点是 dummyHead.next，返回新的链表的头节点即可。指针的调整可以参考如下图示：
完整代码是：
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead.next;
}
class SwapPairs:
def swapPairs(self, head):
dummyHead = ListNode(0)
dummyHead.next = head
temp = dummyHead
while temp.next and temp.next.next:
node1 = temp.next
node2 = temp.next.next
temp.next = node2
node1.next = node2.next
node2.next = node1
temp = node1
return dummyHead.next
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode* temp = dummyHead;
while (temp->next != NULL && temp->next->next != NULL) {
struct ListNode* node1 = temp->next;
struct ListNode* node2 = temp->next->next;
temp->next = node2;
node1->next = node2->next;
node2->next = node1;
temp = node1;
}
struct ListNode* newHead = dummyHead->next;
free(dummyHead);
return newHead;
}
3. 单链表加 1
LeetCode369.用一个非空单链表来表示一个非负整数，然后将这个整数加一。你可以假设这个整数除了 0 本身，没有任何前导的 0。这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
示例:
输入: [1,2,3]
输出: [1,2,4]
我们先看一下加法的计算过程：
计算是从低位开始的，而链表是从高位开始的，所以要处理就必须反转过来，此时可以使用栈，也可以使用链表反转来实现。
基于栈实现的思路不算复杂，先把题目给出的链表遍历放到栈中，然后从栈中弹出栈顶数字 digit，加的时候再考虑一下进位的情况就ok了，加完之后根据是否大于0决定视为下一次要进位 。
public ListNode plusOne(ListNode head) {
Stack<Integer> st = new Stack();
while (head != null) {
st.push(head.val);
head = head.next;
}
int carry = 0;
ListNode dummy = new ListNode(0);
int adder = 1;
while (!st.empty() || carry > 0) {
int digit = st.empty() ? 0 : st.pop();
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
adder = 0;
}
return dummy.next;
}
上面代码，我们简单解释一下，carry的功能是记录进位的，相对好理解 。
那这里的adder是做什么的很多人会感到困惑，这个主要表示就是需要加的数1，也就是为了满足单链表加1的功能，那这里能否直接使用1 ，而不再定义变量呢？也就是将上面的while循环改成这样子：
while (!st.empty() || carry > 0) {
int digit = st.empty() ? 0 : st.pop();
int sum = digit + 1 + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
}
很遗憾，这样不行的，否则的话 ，会将我们每个位置都加1，例如，如果原始单链表是{7,8}这里就会将其变成{8,9},而不是我们要的{7,9}，导致这样的原因是循环处理链表每个结点元素的时候sum = digit + 1 + carry这一行会将每个位置都多加了一个1，所以我们要使用变量adder，只有第一次是加了1，之后该变量变成0了，就不会影响我们后续计算。
class PlusOne:
def plusOne(self, head):
# ans head
ans = ListNode(0)
ans.next = head
not_nine = ans
# find the rightmost not-nine digit
while head:
if head.val != 9:
not_nine = head
head = head.next
not_nine.val += 1
not_nine = not_nine.next
while not_nine:
not_nine.val = 0
not_nine = not_nine.next
return ans if ans.val else ans.next
基于链表反转实现 如果这里不使用栈，使用链表反转来实现该怎么做呢？很显然，我们先将原始链表反转，这方面完成加1和进位等处理，完成之后再次反转。
4. 链表加法
相加相链表是基于链表构造的一种特殊题，反转只是其中的一部分。这个题还存在进位等的问题，因此看似简单，但是手写成功并不容易。
LeetCode445题，给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。示例：
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912
这个题目的难点在于存放是从最高位向最低位开始的，但是因为低位会产生进位的问题，计算的时候必须从最低位开始。所以我们必须想办法将链表节点的元素反转过来。
怎么反转呢？栈和链表反转都可以，两种方式我们都看一下。
(1) 使用栈实现
思路是先将两个链表的元素分别压栈，然后再一起出栈，将两个结果分别计算。之后对计算结果取模，模数保存到新的链表中，进位保存到下一轮。完成之后再进行一次反转就行了。
我们知道在链表插入有头插法和尾插法两种。头插法就是每次都将新的结点插入到head之前。而尾插法就是将新结点都插入到链表的表尾。两者的区别是尾插法的顺序与原始链表是一致的，而头插法与原始链表是逆序的，所以上面最后一步如果不想进行反转，可以将新结点以头插法。
public static ListNode addInListByStack(ListNode head1, ListNode head2) {
Stack<ListNode> st1 = new Stack<ListNode>();
Stack<ListNode> st2 = new Stack<ListNode>();
while (head1 != null) {
st1.push(head1);
head1 = head1.next;
}
while (head2 != null) {
st2.push(head2);
head2 = head2.next;
}
ListNode newHead = new ListNode(-1);
int carry = 0;
//这里设置carry!=0,是因为当st1,st2都遍历完时，如果carry=0,就不需要进入循环了
while (!st1.empty() || !st2.empty() || carry != 0) {
ListNode a = new ListNode(0);
ListNode b = new ListNode(0);
if (!st1.empty()) {
a = st1.pop();
}
if (!st2.empty()) {
b = st2.pop();
}
//每次的和应该是对应位相加再加上进位
int get_sum = a.val + b.val + carry;
//对累加的结果取余
int ans = get_sum % 10;
//如果大于0，就进位
carry = get_sum / 10;
ListNode cur = new ListNode(ans);
cur.next = newHead.next;
//每次把最新得到的节点更新到neHead.next中
newHead.next = cur;
}
return newHead.next;
}
class AddTwoNumbers:
# 使用栈实现
def addTwoNumbers(self, l1, l2):
st1 = []
st2 = []
while l1:
st1.append(l1.val)
l1 = l1.next
while l2:
st2.append(l2.val)
l2 = l2.next
carry = 0
dummy = ListNode(0)
while st1 or st2 or carry:
adder1 = st1.pop() if st1 else 0
adder2 = st2.pop() if st2 else 0
sum = adder1 + adder2 + carry
carry = 1 if sum >= 10 else 0
sum = sum - 10 if sum >= 10 else sum
cur = ListNode(sum)
cur.next = dummy.next
dummy.next = cur
return dummy.next
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* st1 = NULL;
struct ListNode* st2 = NULL;
struct ListNode* curr1 = l1;
struct ListNode* curr2 = l2;
while (curr1 != NULL) {
struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
new_node->val = curr1->val;
new_node->next = st1;
st1 = new_node;
curr1 = curr1->next;
}
while (curr2 != NULL) {
struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode));
new_node->val = curr2->val;
new_node->next = st2;
st2 = new_node;
curr2 = curr2->next;
}
struct ListNode* new_head = (struct ListNode*)malloc(sizeof(struct ListNode));
new_head->val = -1;
new_head->next = NULL;
int carry = 0;
while (st1 != NULL || st2 != NULL || carry != 0) {
struct ListNode* a = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* b = (struct ListNode*)malloc(sizeof(struct ListNode));
if (st1 != NULL) {
a = st1;
st1 = st1->next;
} else {
a->val = 0;
a->next = NULL;
}
if (st2 != NULL) {
b = st2;
st2 = st2->next;
} else {
b->val = 0;
b->next = NULL;
}
int get_sum = a->val + b->val + carry;
int ans = get_sum % 10;
carry = get_sum / 10;
struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode));
cur->val = ans;
cur->next = new_head->next;
new_head->next = cur;
}
struct ListNode* result = new_head->next;
free(new_head);
return result;
}
(2)使用链表反转实现
如果使用链表反转，先将两个链表分别反转，最后计算完之后再将结果反转，一共有三次反转操作，所以必然将反转抽取出一个方法比较好，代码如下：
public class Solution {
public ListNode addInList (ListNode head1, ListNode head2) {
head1 = reverse(head1);
head2 = reverse(head2);
ListNode head = new ListNode(-1);
ListNode cur = head;
int carry = 0;
while(head1 != null || head2 != null) {
int val = carry;
if (head1 != null) {
val += head1.val;
head1 = head1.next;
}
if (head2 != null) {
val += head2.val;
head2 = head2.next;
}
cur.next = new ListNode(val % 10);
carry = val / 10;
cur = cur.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return reverse(head.next);
}
private ListNode reverse(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while(cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
class ReverseList:
def reverseList(self, head) :
prev = None
curr = head
while curr:
nextTemp = curr.next
curr.next = prev
prev = curr
curr = nextTemp
return prev
def addTwoNumbersI(self, l1, l2):
ans = ListNode(0, None)
DUMMY_HEAD, res = ans, 0
p1, p2 = l1, l2
while p1 != None or p2 != None or res == 1:
ans.next = ListNode(0, None)
ans = ans.next
if p1 != None and p2 != None:
sums = p1.val + p2.val
if sums + res < 10:
ans.val = sums + res
res = 0
else:
ans.val = sums + res - 10
res = 1
p1, p2 = p1.next, p2.next
elif p1 == None and p2 != None:
sums = p2.val
if sums + res < 10:
ans.val = sums + res
res = 0
else:
ans.val = sums + res - 10
res = 1
p2 = p2.next
elif p2 == None and p1 != None:
sums = p1.val
if sums + res < 10:
ans.val = sums + res
res = 0
else:
ans.val = sums + res - 10
res = 1
p1 = p1.next
else:
ans.val = res
res = 0
return DUMMY_HEAD.next
#调用入口
def addTwoNumbers(self, l1, l2):
return self.reverseList(self.addTwoNumbersI(self.reverseList(l1), self.reverseList(l2)))
struct ListNode* reverse(struct ListNode* head) {
struct ListNode* cur = head;
struct ListNode* pre = NULL;
while (cur != NULL) {
struct ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
struct ListNode* addTwoNumbers(struct ListNode* head1, struct ListNode* head2){
head1 = reverse(head1);
head2 = reverse(head2);
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = -1;
head->next = NULL;
struct ListNode* cur = head;
int carry = 0;
while (head1 != NULL || head2 != NULL) {
int val = carry;
if (head1 != NULL) {
val += head1->val;
head1 = head1->next;
}
if (head2 != NULL) {
val += head2->val;
head2 = head2->next;
}
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val % 10;
newNode->next = NULL;
cur->next = newNode;
carry = val / 10;
cur = cur->next;
}
if (carry > 0) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = carry;
newNode->next = NULL;
cur->next = newNode;
}
return reverse(head->next);
}
上面我们直接调用了反转函数，这样代码写起来就容易很多，如果你没手写过反转，所有功能都是在一个方法里，那复杂度要高好几个数量级，甚至自己都搞不清楚了。
既然加法可以，那如果是减法呢？读者可以自己想想该怎么处理。
5. 再论链表的回文序列问题
在上一关介绍链表回文串的时候，我们介绍的是基于栈的，相对来说比较好理解，但是除此之外还有可以使用链表反转来进行，而且还可以只反转一半链表，这种方式节省空间。
我们姑且称之为“快慢指针+一半反转”法。
这个实现略有难度，主要是在while循环中pre.next = prepre和prepre = pre两行实现了一边遍历一边将访问过的链表给反转了，所以理解起来有些难度，如果不理解可以在学完链表反转之后再看这个问题。
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
//将前半部分链表反转
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
def isPalindrome(self, head):
fake = ListNode(-1)
fake.next = head
fast = slow = fake
while fast and fast.next:
fast = fast.next.next
slow = slow.next
post = slow.next
slow.next = None
pre = head
rev = None
# 反转
while post:
tmp = post.next
post.next = rev
rev = post
post = tmp
part1 = pre
part2 = rev
while part1 and part2:
if part1.val != part2.val:
return False
part1 = part1.next
part2 = part2.next
return True
bool isPalindrome(struct ListNode* head){
if (head == NULL || head->next == NULL) {
return true;
}
struct ListNode* slow = head;
struct ListNode* fast = head;
struct ListNode* pre = head;
struct ListNode* prepre = NULL;
while (fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
// 将前半部分链表反转
pre->next = prepre;
prepre = pre;
}
if (fast != NULL) {
slow = slow->next;
}
while (pre != NULL && slow != NULL) {
if (pre->val != slow->val) {
return false;
}
pre = pre->next;
slow = slow->next;
}
return true;
}阅读量：1858
点赞量：0
收藏量:0