Ex_1_3_30.md

title	date	draft	tags	categories
Algorithm4 Java Solution 1.3.30	2019-07-04 05:47:10 +0800	false	JAVA	TECH archives

1.3.30

Problem:

Write a function that takes the first Node in a linked list as argument and (destructively) reverses the list, returning the first Node in the result.

Solution：

To accomplish this task, we maintain references to three consecutive nodes in the linked list, reverse, first, and second. At each iteration, we extract the node first from the original linked list and insert it at the beginning of the reversed list. We maintain the invariant that first is the first node of what’s left of the original list, second is the second node of what’s left of the original list, and reverse is the first node of the resulting reversed list.

Reference：