LeetCode 92. 反转链表 II

一时失言乱红尘 2022-11-10 14:27 126阅读 0赞

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：
    
    
    输入：head = [1,2,3,4,5], left = 2, right = 4
    输出：[1,4,3,2,5]
    示例 2：
    
    输入：head = [5], left = 1, right = 1
    输出：[5]
     
    
    提示：
    
    链表中节点数目为 n
    1 <= n <= 500
    -500 <= Node.val <= 500
    1 <= left <= right <= n
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.  为链表创建新的头结点，以便所有可能情况进行统一处理；
2.  循环找到左节点leftNode及左节点前面的一个结点leftpre；
3.  继续循环，找到右结点rightNode及右结点的next结点p；
4.  利用链表翻转函数（递归翻转）将leftNode~rightNode区间的链表翻转；
5.  leftpre.next连接rightNode;
6.  leftNode.next连接p;
7.  返回newhead头结点的next即可。

/**
     * 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) {
        
        	if(left==right) return head;
        	int cnt=1;
        	ListNode leftNode=null;
        	ListNode newhead=new ListNode(0);
        	newhead.next=head;
        	ListNode leftpre=newhead;
        	ListNode rightNode=null;
        	ListNode p=head;
        	while(cnt<left) {
        
        		leftpre=leftpre.next;
        		p=p.next;
        		cnt++;
        	}
        	leftNode=p;
        	while(cnt<right) {
        
        		p=p.next;
        		cnt++;
        	}
        	rightNode=p;
        	p=p.next;
        	rightNode.next=null;
        	dfs(leftNode);
        	leftpre.next=rightNode;
        	leftNode.next=p;
        	return newhead.next;
        }
        public ListNode dfs(ListNode head) {
        
    		if(head==null) return new ListNode(0);
    		ListNode tmp=dfs(head.next);
    		tmp.next=head;
    		head.next=null;
    		return head;
    	}
    }