【LEETCODE】模拟面试-206. Reverse Linked List
【LEETCODE】模拟面试-206. Reverse Linked List
图：新生大学
https://leetcode.com/problems/reverse-linked-list/
Reverse a singly linked list.
**input: **a single linked list output: a list node head of the reverse list of given input **corner: **when the list is null, or only contains one head
What we want to do is to reverse the list.
So we scan from head to tail.
For every two nodes cur and cur.next, we will make cur point to its forward node.
So at each step, we need a node pre to keep connection with current scanner, so that cur.next = pre.
And we also need a node nextOne to memorize cur.next, since it will be changed during the scanner, if without track, cur will lose its way to next scanner.
In order to move to next scanner, pre will move to cur, and cur will move to nextOne.
Until cur moves to tail null, pre is currently the new head of the reversed list, so just return it.
The idea of Recursion is similar with Iteration, what to do in current scanner is to keep track of nextOne and point to pre, and what to prepare for next step is to pass nextOne and cur as the new 'cur' and 'pre'.
//iteration
public class Solution{
public ListNode reverseList(ListNode head){
//corner
if ( head == null || head.next == null ){
return head;
}
ListNode pre = null;
ListNode cur = head;
while ( cur != null ){
//reverse
ListNode nextOne = cur.next;
cur.next = pre;
//prepare
pre = cur;
cur = nextOne;
}
return pre;
}
}
//recursion
public class Solution{
public ListNode reverseList(ListNode head){
//corner
if ( head == null || head.next == null ){
return head;
}
ListNode pre = null;
return helper(head, pre);
}
public ListNode helper(ListNode cur, ListNode pre){
//base
if ( cur == null ){
return pre;
}
//current
ListNode nextOne = cur.next;
cur.next = pre;
//next
return helper(nextOne, cur);
}
}腾讯云开发者
