Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
solve.cpp

README.md

Reverse Linked List

Reverse a singly linked list.

click to show more hints. Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

迭代法:

ListNode *reverseIteratively(ListNode *head) {
	if (!head || !head->next)
		return head;
	ListNode *prev = nullptr, *p = head;
	while (p) {
		ListNode *q = p->next;
		p->next = prev;
		prev = p;
		p = q;
	}
	return prev;
}

递归法,注意更新head指针:

ListNode *reverseRecursively(ListNode *&head, ListNode *p) {
	if (!p|| !p->next) {
		head = p;
		return head;
	}
	reverseRecursively(head, p->next)->next = p;
	p->next = nullptr;
	return p;
}

扩展

Reverse Linked List II: 逆转指定的区间

You can’t perform that action at this time.