[数据结构与算法]反转链表+反转前N个链表+反转指定索引下的局部链表

反转链表+反转前N个链表+反转指定索引下的局部链表

反转链表

https://leetcode.cn/problems/reverse-linked-list/

迭代式算法:(不作过多赘述)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        return prev;
    }
}

递归式写法:

class Solution {
    public ListNode reverseList(ListNode head) {
        //base case
        if(head==null||head.next==null) return head;
        
        ListNode last=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return last;
    }
}

Note:写递归时,要明确递归函数在干嘛?上述的递归可以这样理解:

不要跳进递归,递归函数总是能把传入的头节点往后的所有节点进行反转,并返回反转之后的头节点,这也是题意,这里重要的是base case,我们必须把基本情况考虑详尽才不会出现递归错误,这里的情况还是很容易看的,只有一个节点,反转后还是自己,没有节点,当然返回null.

至于上述7/8行代码看图理解咯!~

反转单链表的前N个节点

在上一题的基础之上,如何考虑反转前N个节点呢?

只要在上述代码稍加改动即可.没有对应的题,我们可以假设一个题干或者说标签,题意就是:反转从head开始的n个节点,并返回最前面的节点.

public ListNode reverseListN(ListNode head,int n)

再画个图吧~:

比如上图:

reverseListN(head,3)就应当反转前3个节点,并返回3

对题1改动后,直接见代码:

class Solution {
    ListNode successor=null;
    public ListNode reverseList(ListNode head,int n) {
        //base case
        if(n==1){
            successor=head.next;//记录当前head的后一个节点
            return head;//只有一个节点时直接返回咯
        }

        ListNode last=reverseList(head.next,n-1);
        head.next.next=head;
        head.next=successor;
        return last;
    }
}

Note:代码中的successor就是如图中的4节点

反转单链表中的局部若干连续子串

有了上面两题的加持,这里就容易很多

https://leetcode.cn/problems/reverse-linked-list-ii/

可以这样理解:

我们的目的就是在上面两道题的基础之上,把这道题写出来(虽然迭代可以写,但有很多细节.递归更省心)

1. 寻求从哪个节点开始反转
2. 然后利用前N个节点反转的情况即可完成目的
3. 见代码:

class Solution {
    ListNode successor=null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //if(head==null||head.next==null) return head;
        if(left==1){
            return reverseListN(head,right);
        }
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;
    }
    private ListNode reverseListN(ListNode head,int n){
        //if(head==null||head.next==null) return head;
        if(n==1){
            successor=head.next;
            return head;
        }
        ListNode last=reverseListN(head.next,n-1);
        head.next.next=head;
        head.next=successor;
        return last;
    }
}

(注释部分写于不写都是对的,为什么不写是对的不再赘述,平时写时可以都写上,以防万一)

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖