题目内容
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?
分析过程
-
题目归类：
-
题目分析：
-
边界分析：
- 空值分析
- 循环边界分析
-
方法分析：
- 数据结构分析
- 状态机
- 状态转移方程
- 最优解
-
测试用例构建
代码实现
非递归
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head != null){
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
}
递归
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode tmp = reverseList(head.next);
head.next.next = head;
head.next = null;
return tmp;
}
}
效率提高
拓展问题
Reverse Linked List II
Medium
Binary Tree Upside Down
Medium
Palindrome Linked List
Easy