将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 ,空间复杂度 。
例如:
给出的链表为 , ,
返回 .
例如:
给出的链表为 , ,
返回 .
数据范围: 链表长度 ,,链表中每个节点的值满足
要求:时间复杂度 ,空间复杂度
进阶:时间复杂度 ,空间复杂度
public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode pre=new ListNode(0) ,p1=pre; pre.next=head; for(int i=1;i<m;i++){ p1=p1.next; } ListNode p2=p1.next ,temp=p1.next; for(int i=m;i<=n;i++){ ListNode node=p2.next; p2.next=p1.next; p1.next=p2; p2=node; } temp.next=p2; return pre.next; }
public ListNode reverseBetween (ListNode head, int m, int n) { // write code here if (head == null || m >= n) { return head; } ListNode rootNode = new ListNode(0); rootNode.next = head; ListNode pre = null; ListNode mNode = null; ListNode nNode = null; ListNode mmNode = null; int k = 1; int j = 0; while(k <= n && head!= null){ if (k+1 == m){ mNode = head; mmNode = head.next; j++; }else if(k == m && j == 0){ mNode = rootNode; mmNode = head; } if (k == n){ nNode = head.next; } if (k >= m && k <= n){ ListNode temp = head.next; head.next = pre; pre = head; head = temp; }else{ head = head.next; } k++; } mNode.next = pre; mmNode.next = nNode; return rootNode.next; // 返回链表的头节点 }为解题而解题硬凑的,算法还是Java排第一的那个妙
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode tmp = head; ListNode pre, cur, preNode = null, tailNode = null; int i = 0; //范围包含头结点,则创建一个结点使得 next 域指向 head if (m == 1) { preNode = new ListNode(0); preNode.next = head; } //遍历链表找到起始节点 while (tmp != null) { //若范围不包含头节点,则记录范围两头相邻的节点preNode、tailNode if (i == m - 2) { preNode = tmp; } if (i == n) { tailNode = tmp; } tmp = tmp.next; i++; } pre = null; cur = preNode.next; //反转链表 while (cur != null) { if (cur == preNode.next) { pre = tailNode; } tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; if (cur == tailNode) { preNode.next = pre; break; } } if (m == 1) { return preNode.next; } return head; } }
public class Solution {
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * *
@param head ListNode类
@param m int整型
@param n int整型
@return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here ListNode root = new ListNode(-1); root.next = head; ListNode left = null; ListNode right = null; ListNode begin = root; ListNode end = root; for(int i=0;i<m;i++){ left = begin; begin = begin.next; } for(int i=0;i<n;i++){ end = end.next; right = end.next; } left.next = null; end.next = null; reverseNode(begin); left.next = end; begin.next = right; return root.next;
}
public ListNode reverseNode (ListNode head){
if(head == null) { return null; } ListNode pre = null; ListNode next = null; while(head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre;
}
}
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { ListNode pre=new ListNode(-1); pre.next=head; ListNode cp=head; ListNode cur=head; ListNode start=pre; int left=1; while(left<m){start=cp;cp=cp.next;cur=cur.next;left++;} while(left<n){cur=cur.next;left++;} ListNode last=cur.next; int s=m; while(s<=n){ ListNode next=cp.next; cp.next=last; last=cp; cp=next; s++; } start.next=cur; return pre.next; // write code here } }
public ListNode reverseBetween (ListNode head, int m, int n) { //此情况无需反转 if(m == n ) { return head; } //虚拟节点,防止从第一个节点就开始反转(m=1的情况) ListNode res = new ListNode(-1); res.next = head; //指针,指向反转节点的 前一个节点,用于连接 反转后的节点 ListNode perfix = res; ListNode p = head; //找到第一个反转的开始节点 while(p.next != null && m > 1) { p = p.next; perfix = perfix.next; m--; n--; } ListNode reversNode = null; //开始反转 while(p != null && n > 0) { ListNode tmp = p.next; p.next = reversNode; reversNode = p; p = tmp; n--; } //reversNode 就是反转后的节点 perfix.next = reversNode; ListNode s = reversNode; //指针s,找到反转后的链表 的最后一个节点 while (s.next != null) { s = s.next; } //将这个节点连接上p s.next = p; return res.next; }
import java.util.*; public class Solution { public ListNode reverseBetween (ListNode head, int m, int n) { // dummy -> l1 -> l2 -> l3, 反转 l2 ListNode dummy = new ListNode(-1); dummy.next = head; // 断开 ListNode p = dummy; int idx = 0; while ( idx < m-1 ) { p = p.next; idx ++; } ListNode l1Tail = p, l2Head = p.next; p.next = null; // 断开 p = l2Head; while ( idx < n-1 ) { p = p.next; idx ++; } ListNode l3Head = p.next; p.next = null; ListNode[] headTail = reverse(l2Head); l1Tail.next = headTail[0]; headTail[1].next = l3Head; return dummy.next; } ListNode[] reverse(ListNode head) { ListNode pre = null, cur = head, nxt = null; while ( cur != null ) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } return new ListNode[]{pre, head}; } }
// 方法一: public ListNode reverseBetween (ListNode head, int m, int n) { // 用于指向头结点,在完成反转后返回,防止头节点丢失 ListNode dummy = new ListNode(-1); // next指向头节点 dummy.next = head; ListNode pre = dummy; // 将pre移至m节点的前一个节点 for(int i= 1;i<m;i++){ pre = pre.next; } // 指向m节点 ListNode cur = pre.next; // 初始化cur节点的下一节点 ListNode temp = null; // 进行n-m次反转,反转过程中,cur节点一直不变,因为cur节点最终会位于反转链的末尾, // 每一次循环都完成一次将原cur链中cur节点的下一节点放至反转链的头节点位置,并与pre节点拼接的过程 for(int i = 0;i<(n-m);i++){ temp = cur.next; //cur节点指向它的下下节点,即删除pre链和cur链中的temp节点(cur的下一个节点) cur.next = temp.next; // 使temp节点指向pre节点的下一节点,即在pre节点的一下节点前拼接temp节点 temp.next = pre.next; // 在pre节点后拼接temp链 pre.next = temp; } // 如果从第一个节点开始反转,此时pre = dummy,则pre.next = temp即为dummy.next = temp,首节点会变化 // 如果不是从第一个节点开始反转,则pre != dummy,则dummy.next = head,而head在反转过程中未发生变化,首节点不变化 // 这保证了dummy一直指向头结点,因此不返回head或者pre,而是返回dummy.next return dummy.next; } // 方法二: // 为什么我想的这么复杂!!!! public ListNode reverseBetween2 (ListNode head, int m, int n) { // 用于计数 int count = 0; // 当前节点 ListNode cur = head; // 反转串的头结点 ListNode headOfReverse = null; // 反转串的尾节点 ListNode tailOfReverse = null; // 从首节点后任意节点开始反转 if (m > 1) { // 反转串前第一个不反转的节点 ListNode node = null; while (count <= n) { count++; // 记录反转串的尾节点 if (count == m) tailOfReverse = cur; // 开始反转 if (count >= m && count <= n) { ListNode temp = cur.next; cur.next = headOfReverse; headOfReverse = cur; cur = temp; // 未开始反转时 } else if (count<n){ // 记录反转串前第一个不反转的节点 node = cur; // 当前节点后移 cur = cur.next; } } // 拼接反转串前第一个不反转的节点与反转串 node.next = headOfReverse; // 拼接反转串的尾节点与反转串后不反转的节点 tailOfReverse.next = cur; // 返回原头结点 return head; // 首节点开始反转 } else { cur = head; while (count <= n) { count++; // 记录反转串的尾节点 if (count == m) tailOfReverse = head; // 开始反转 if (count >= m && count <= n) { ListNode temp = cur.next; cur.next = headOfReverse; headOfReverse = cur; cur = temp; } } // 拼接反转串的尾节点与反转串后不反转的节点 tailOfReverse.next = cur; // 反转串的头节点成为新的头节点,返回反转串的头结点 return headOfReverse; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { // write code here //res 用于保存最终结果 ListNode res = new ListNode(-1); ListNode tail = res; ListNode p = head; for (int i = 1; i < m; i++) { ListNode tmp = p.next; tail.next = p; tail = p; p.next = null; p = tmp; } ListNode s = null; for (int j = m; j <= n; j++) { ListNode tmp = p.next; p.next = s; s = p; p = tmp; } tail.next = s; ListNode cur=s; while(cur.next!=null){ cur=cur.next; } if (p != null) { cur.next = p; } return res.next; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { if (head == null) { return null; } //创建一个虚拟头节点,让整个单链表所有结点处在统一地位方便逻辑处理,dum是一个指向这个链表头结点的指针,它指向的结点的值为0 ListNode dum = new ListNode(0); dum.next = head; ListNode pre = dum; ListNode cur = head; //找到m结点 //过程中,随着cur往链表右边移动,pre指针同样也存储了1到m结点的指向 for (int i = 1; i < m; i++) { pre = cur; cur = cur.next; } for (int j = 0; j < n - m; j++) { ListNode zc = cur.next; cur.next = zc.next; zc.next = pre.next; pre.next = zc; } // write code here return dum.next; } }
import java.util.*; public class Solution { public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode dummy = new ListNode(-1); dummy.next = head; //m前一个节点 ListNode first = dummy; int id = 0; while(id++<m-1){ first = first.next; } //m节点 ListNode second = first.next; ListNode cur = second; ListNode pre = null; //n这个节点需要进入,因为是当前节点往前反转 while(id++<=n){ ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } //出来后,pre就是n节点,cur就是n后面的节点 //first连接pre first.next = pre; //second连接cur second.next = cur; return dummy.next; } }
public class Solution { /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ //本题难点:空指针问题和控制反转区间 //可以加入头结点来解决反转区间的问题(主要是解决从head到n区间的问题) //思路:先找到反转区间的前一个结点和末尾的后一个结点,方便连接 //然后对反转区间进行迭代头插法(注意控制次数),最后进行连接。 //时间O(N),空间O(1) public ListNode reverseBetween (ListNode head, int m, int n) { if(m==n) { return head; } ListNode Head=new ListNode(-1); ListNode head1=Head;//分别记录区间的前一个,和末尾的后一个 ListNode tail1=head; Head.next=head; int n1=n; int m1=m-1; while(m1>0) { head1=head1.next; m1--; } while(n1>0) { tail1=tail1.next; n1--; } ListNode head2=null;//反转区间的头结点 //cur和tmp用来迭代 ListNode cur=head1.next; ListNode tmp=cur; int num=n-m+1; while(num>0) { tmp=cur.next; if(head2==null) { head2=cur; cur.next=tail1; } else { cur.next=head2; head2=cur; } cur=tmp; num--; } if(head1!=null) head1.next=head2; return Head.next; } }