LinkedList - 206. Reverse Linked List
- Reverse Linked List
Reverse a singly linked list.
Example:
**Input:** 1->2->3->4->5->NULL
**Output:** 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
思路：
翻转链表。主要有两种方法，迭代和递归。递归就是不断的把当前节点指向前一个链表的新头节点，递归出口是当前节点为nil。迭代的做法是两个指针往后滑动，保存好当前节点的下一个节点，避免断链。
代码：
golang:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseListRecurese(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
return reverse(head, nil)
}
func reverse(head, newHead *ListNode) *ListNode {
if head == nil {
return newHead
}
tmp := head.Next
head.Next = newHead
return reverse(tmp, head)
}
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var newHead *ListNode
for head != nil {
tmp := head.Next
head.Next = newHead
newHead = head
head = tmp
}
return newHead
}
java：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// iterative
/* public ListNode reverseList(ListNode head) {
if (head == null) return head;
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}*/
// recursive
public ListNode reverseList(ListNode head) {
return reverseListInt(head, null);
}
private ListNode reverseListInt(ListNode head, ListNode newHead) {
if (head == null)
return newHead;
ListNode next = head.next;
head.next = newHead;
return reverseListInt(next, head);
}
}```