算法通关村第二关-白银挑战反转链表拓展问题

大家好我是苏麟 , 今天聊一聊链表反转拓展问题 . 

反转链表拓展问题

1.指定区间反转

描述 : 

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

题目 :

LeetCode 92.反转链表 : 

92. 反转链表 II
 

牛客 BM2 链表内指定区间反转 : 

分析 : 

这里的处理方式也有多种，甚至给个名字都有点困难，干脆就分别叫穿针引线法和头插法吧。穿针引线本质上就是不带有节点的方式来实现反转，而头插法本质上就是带头结点的反转。

头插法

这个方法的缺点是:

如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)，但遍历了链表 2次，p不可以只遍历一次呢? 答案是可以的。我们依然画图进行说明，我们仍然以方法一的序列为例进行说明。

反转的整体思想是，在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。
下面的图展示了整个流程。

这个过程就是前面的带虚拟结点的插入操作，每走一步都要考虑各种指针怎么指，既要将结点摘下来接到对应的位置上，还要保证后续结点能够找到，请读者务必画图看一看，想一想到底该怎么调整。

代码如下 :

/*** 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;}
}

2.单链表加一

描述 : 

给定一个用单链表表示的整数，然后把这个整数加一。

题目 :

LeetCode  66.加一 :

66. 加一

LeetCode 369.给单链表加一 :

 369. 给单链表加一

牛客 NC189 给单链表加一 :

分析 : 

我们先看一下加法的计算过程:
计算是从低位开始的，而链表是从高位开始的，所以要处理就必须反转过来，此时可以使用栈，也可以使用链表反转来实现。
基于栈实现的思路不算复杂，先把题目给出的链表遍历放到栈中，然后从栈中弹出栈顶数字 digit，加的时候再考虑一下进位的情况就ok了，加完之后根据是否大于0决定视为下一次要进位 .

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/public ListNode plusOne (ListNode head) {// write code here/**把数字压入栈中*/Stack<Integer> s = new Stack<>();while(head!=null){s.push(head.val);head = head.next;}ListNode d = new ListNode(-100);ListNode p = d;//carry代表进位int carry = 0;//x代表要加的1int x = 1;while(!s.empty() || carry == 1){int y = s.empty() ? 0 : s.pop() ;int num = carry + x + y;carry = num >= 10 ? 1 : 0;num = num >= 10 ? num-10 : num;//头插ListNode temp = new ListNode(num);temp.next = p.next;p.next = temp;x = 0;}return d.next;}
}

基于链表反转实现 如果这里不使用栈，使用链表反转来实现该怎么做呢?很显然，我们先将原始链表反转，这方面完成加1和进位等处理，完成之后再次反转。本实现作为一个作业，请读者完成。

这期就到这里 , 下一关见!