92. 反转链表 II

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 131 阅读时长 ≈ 1 分钟

考点

  • 链表的反转

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public:
		ListNode* reverseBetween(ListNode* head, int left, int right) {
			ListNode *dummyHead = new ListNode(-1, head), *subDummy = dummyHead;
			for (int i = 0; i < left - 1; i++) subDummy = subDummy->next;
            //使用改进版头插法进行子链表反转
			ListNode *tail = subDummy->next;
			for (int i = 0; i < right - left; i++) {
				ListNode *node = tail->next;
				tail->next = node->next;
				node->next = subDummy->next;
				subDummy->next = node;
			}
			return dummyHead->next;
		}
};

思路

找到子链表的头节点，并将其前一个节点作为伪节点，即subDummy；再使用206. 反转链表提到的改进版头插法即可