Leetcode Answers 206

今天第二道,也是一道Easy题,反转LinkedList。

题目:
Reverse a singly linked list.

思路:
又是一句话问题。下面有个hint是既可以iteratively也可以recursively处理,本着减少递归的思想,先搞迭代。那么就是准备两个pointer,一个指向当前,一个指向next,然后把next的next指向当前,再把当前挪到原来的next的next上,那么就需要第三个tmp pointer。

Answer:

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

思路2:
那么换个思路,如果想要递归处理的话怎么弄?当pointer指向null的时候就是到末尾了,不然就是交换前后两个pointer,并继续传递下去。

Answer2:(Java版本,然而和C#长得没啥区别。。。)

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

没啥可考察的,算是基本功。

以上。

17-04-25
@Sturbridge