LeetCode 92. 反转链表 II
2021-09-08 本文已影响0人
陈陈chen
1、题目
image.png
2、分析
思路一：
1、把链表中的正整数都保存到一个数组中。后面直接用数组中的值来重新构造链表
2、left前面的元素不变，直接构造链表
3、left和right中的元素，从right - 1的元素开始往前构造到left - 1
4、right后面的元素不变，直接构造链表
思路二：
image.png
1、记录下反转段链表的前一个节点pre和后一个节点succ。找到left和right节点
2、将待反转链表反转
3、将反转后的链表，跟pre和succ拼接起来
思路三：
使用递归的方法。但是递归的方法比较难以理解。
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) {
//先把链表中的值，保存到数组中
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个元素，不用反转，直接构造
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开始，往前遍历数组，一直到left - 1个元素为止，构造链表。这里就是反转的链表了
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元素开始，不用反转，直接构造到最后一个
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) {
//构造一个虚拟节点，这样就不用特殊处理left = 1的情况
ListNode fakeNode = new ListNode(-1);
fakeNode.next = head;
ListNode pre = fakeNode;
//找到pre节点
for(int i = 0; i < left - 1; i++){
pre = pre.next;
}
ListNode leftNode = pre.next;
//找到succ节点
ListNode succ = leftNode;
for(int i = 0; i < right - left; i++){
succ = succ.next;
}
//反转链表
ListNode rightNode = succ;
succ = succ.next;
rightNode.next = null;
reverseLinkedList(leftNode);
//拼接链表
pre.next = rightNode;
leftNode.next = succ;
return fakeNode.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;
}
}
}
