翻转链表中第m个节点到第n个节点的部分
注意事项:
m
,n
满足1 ≤ m ≤ n ≤ 链表长度
给出链表 1->2->3->4->5->null
, m = 2
和 n = 4
,返回 1->4->3->2->5->null
本题类似于 翻转链表,只不过是限定了翻转的个数而已。
可以先记录下 m
节点的前一个节点,与 n
节点的后一个节点,然后将 m - n
进行翻转(参考:翻转链表 ),最后利用 m
的前节点和 n
的后节点,将链表再次链接起来即可。
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @oaram m and n
* @return: The head of the reversed ListNode
*/
public ListNode reverseBetween(ListNode head, int m , int n) {
//非空判断
if (m >= n || head == null) {
return head;
}
ListNode dummy = new ListNode(0); // 插入头节点
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++) { // 找到m节点前面一个节点
if (head == null) {
return null;
}
head = head.next;
}
ListNode premNode = head; // m 之前的那个节点
ListNode mNode = premNode.next; // m 节点
ListNode nNode = mNode;// n节点
ListNode postnNode = mNode.next; // n 之后那个节点
// n 后节点 插入到n 节点之前
for (int i = m; i < n; i++) {
if (postnNode == null) {
return null;
}
ListNode temp = postnNode.next; // 下一个节点
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
mNode.next = postnNode;// m next 指向 n 后
premNode.next = nNode; // m 前节点 指向 n
return dummy.next;
}
}