1、題目
image.png
2、分析
思路一：
1、把鏈表中的正整數(shù)都保存到一個(gè)數(shù)組中。后面直接用數(shù)組中的值來(lái)重新構(gòu)造鏈表
2、left前面的元素不變，直接構(gòu)造鏈表
3、left和right中的元素，從right - 1的元素開始往前構(gòu)造到left - 1
4、right后面的元素不變，直接構(gòu)造鏈表
思路二：
image.png
1、記錄下反轉(zhuǎn)段鏈表的前一個(gè)節(jié)點(diǎn)pre和后一個(gè)節(jié)點(diǎn)succ。找到left和right節(jié)點(diǎn)
2、將待反轉(zhuǎn)鏈表反轉(zhuǎn)
3、將反轉(zhuǎn)后的鏈表，跟pre和succ拼接起來(lái)
思路三：
使用遞歸的方法。但是遞歸的方法比較難以理解。
3、代碼
思路一代碼：
/**
* 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) {
//先把鏈表中的值，保存到數(shù)組中
List<ListNode> arry = new ArrayList<ListNode>();
while(head != null)
{
arry.add(head);
head = head.next;
}
ListNode res = new ListNode();
ListNode cur = null;
//從0開始，到left - 2個(gè)元素，不用反轉(zhuǎn)，直接構(gòu)造
for (int i = 0; i < left - 1; i++){
ListNode tmp = arry.get(i);
if(cur == null)
{
cur = tmp;
res = tmp;
}
cur.next = tmp;
cur = tmp;
}
//從right - 1開始，往前遍歷數(shù)組，一直到left - 1個(gè)元素為止，構(gòu)造鏈表。這里就是反轉(zhuǎn)的鏈表了
for (int i = right - 1; i >= left - 1; i--){
ListNode tmp = arry.get(i);
if(cur == null)
{
cur = tmp;
res = tmp;
}
cur.next = tmp;
cur = tmp;
}
//從right元素開始，不用反轉(zhuǎn)，直接構(gòu)造到最后一個(gè)
for (int i = right; i < arry.size(); i++){
ListNode tmp = arry.get(i);
if(cur == null)
{
cur = tmp;
res = tmp;
}
cur.next = tmp;
cur = tmp;
}
cur.next = null;
return res;
}
}
思路二代碼：
/**
* 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) {
//構(gòu)造一個(gè)虛擬節(jié)點(diǎn)，這樣就不用特殊處理left = 1的情況
ListNode fakeNode = new ListNode(-1);
fakeNode.next = head;
ListNode pre = fakeNode;
//找到pre節(jié)點(diǎn)
for(int i = 0; i < left - 1; i++){
pre = pre.next;
}
ListNode leftNode = pre.next;
//找到succ節(jié)點(diǎn)
ListNode succ = leftNode;
for(int i = 0; i < right - left; i++){
succ = succ.next;
}
//反轉(zhuǎn)鏈表
ListNode rightNode = succ;
succ = succ.next;
rightNode.next = null;
reverseLinkedList(leftNode);
//拼接鏈表
pre.next = rightNode;
leftNode.next = succ;
return fakeNode.next;
}
//反轉(zhuǎn)鏈表函數(shù)
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;
}
}
}
