Similar Questions 

   

 

思路：链表反转。

解法一：迭代。

添加头节点（推荐）：不断将当前元素start插入dummy和dummy.next之间，实现反转。

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode reverseList(ListNode head) {11         if(head == null) return head;12         ListNode dummy = new ListNode(0);13         dummy.next = head;14         ListNode pre = head, start = head.next;15         while(start != null) {16             pre.next = start.next;17             start.next = dummy.next;18             dummy.next = start;19             start = pre.next;20         }21         return dummy.next;22     }23 }

 

不添加头节点：

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode reverseList(ListNode head) {11         ListNode p0, p1;12         p0 = null;13         p1 = head;14         while(p1 != null) {
   //确保p1不为空15             ListNode p2 = p1.next;16             p1.next = p0;17             p0 = p1;18             p1 = p2;19         }20         return p0;21     }22 }

解法二：递归。

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode reverseList(ListNode head) {11         if(head == null || head.next == null) return head;//这个判断很重要12         ListNode p1 = head.next;13         ListNode p0 = reverseList(p1);14         p1.next = head;15         head.next = null;16         return p0;17     }18 }

Next challenges: