LeetCode 92. 反转链表 II

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 92. 反转链表 II

思路分析

找到反转链表的起始节点的前一个节点

反转指定区间的链表

连接左右两部分

参考代码

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || head.Next == nil || left == right {
		return head
	}

	dummy := &ListNode{Next: head} // 创建虚拟头节点
	first := dummy

	// 移动 first 指针到需要反转部分的前一个节点
	for i := 1; i < left; i++ {
		first = first.Next
	}

	var pre *ListNode
	cur := first.Next

	// 反转从 left 到 right 的节点
	for i := left; i <= right; i++ {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	// 将反转后的部分连接回原链表
	first.Next.Next = cur
	first.Next = pre

	return dummy.Next // 返回虚拟头节点的下一个节点，即反转后的链表头节点
}

时间复杂度：O (n)，其中 n 是链表的长度。我们只遍历链表一次。

空间复杂度：O (1)，我们只使用了常数级别的额外空间。

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	if head == nil || head.Next == nil || m == n {
		return head
	}

	dummy := &ListNode{Next: head}
	pre := dummy

	// 找到反转的起始节点
	for i := 1; i < m; i++ {
		pre = pre.Next
	}

	// 反转链表的部分
	cur := pre.Next
	var next *ListNode
	for i := 0; i < n-m; i++ {
		next = cur.Next
		cur.Next = next.Next
		next.Next = pre.Next
		pre.Next = next
	}

	return dummy.Next
}

// 辅助函数：打印链表
func printList(head *ListNode) {
	for head != nil {
		fmt.Print(head.Val, " -> ")
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := &ListNode{Val: 1}
	head.Next = &ListNode{Val: 2}
	head.Next.Next = &ListNode{Val: 3}
	head.Next.Next.Next = &ListNode{Val: 4}
	head.Next.Next.Next.Next = &ListNode{Val: 5}

	fmt.Println("原链表:")
	printList(head)

	newHead := reverseBetween(head, 2, 4)
	fmt.Println("反转后的链表:")
	printList(newHead)
}

时间复杂度：O (n)，其中 n 是链表的长度。我们只遍历链表一次。

空间复杂度：O (1)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left >= right) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode start = dummy;

        for (int i = 1; i < left; i++) {
            start = start.next;
        }

        ListNode pre = null, cur = start.next;
        for (int i = left; i <= right; i++) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        start.next.next = cur;
        start.next = pre;
        return dummy.next;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/92836975