链表的算法

题目

将一个节点数为 size 链表 m 位置到 n位置之间的区间反转，

要求时间 复杂度 O(n)，空间复杂度 O(1)。

例如: 给出的链表为1→2→3→4→5→NUL,m=2,n=4

返回1→>4→>3→2->5->NULL

, 数据范围:链表长度0< size < 1000,0 <m<n< size，链表 中每个节点的值满足 val < 1000

空间复杂度 O(n) 要求:时间复杂度 O(n)， 进阶:时间复杂度 O(n)，空间复杂度 O(1)

来自牛客网

解析

目的反转一个给定链表中从位置m到n的字链表。

1.首先，创建一个虚拟头节点dummy，它的next指向head。这样做的目的是在反转过程中保持原始头节点不变，方便最后返回结果。

2.初始化一个指针prev指向dummy，用于遍历过程中纪录前一个节点。

3.循环遍历

4.检查prev是否为null

5.定义start为反转子链表的起始节点，then为start的下一个节点

6.循环遍历n-m次

start的next的指针指向then的下一个节点

then的next的指针指向prev的next

prev的next指针为then

then为start的next

7返回。

代码

import java.util.*
 
class ListNode{
    int val;
    ListNode next;
    ListNode next;
    ListNode(int val){
        this.val=val;
    }
}

public class Solution{
    public ListNode reverseBetween(ListNode head ,int m,int n){
        if(head == null || m>=n){
            return head;
        }
        ListNode dummy =new ListNode(-1);
        dummy.next =head;
        ListNode prev =dummy;
        //找到要反转区间的前一节点
        for(int i=0;i<m-1&&prev!=null;i++){
            prev=prev.next;
        }
        if(prev==null || prev.next==null){
            return head;
        }
        ListNode start=prev.next;
        ListNode then=start.next;

        //开始反转区间
        for(int i=0;i<n-m;i++){
            start.next=then.next;
            then.next=prev.next;
            prev.next =then;
            then =start.next;
        }
return dummy.next;
    }
}

总结

   不断练习