面试题24. 反转链表
难度简单
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
考虑边界条件：
- 链表为空
- 链表只包含一个节点的情况
第一种解答：
递归法:
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;
}
}
第二种解法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = null, pre = head;
ListNode temp = null;
while(pre != null){
temp = pre.next;
pre.next = cur;
cur = pre;
pre = temp;
}
return cur;
}
}
第二种解答：
另一个版本的双指针法：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return head;
ListNode pre, cur;
cur = head;
while(head.next != null){
pre = head.next.next;
head.next.next = cur;
cur = head.next;
head.next = pre;
}
return cur;
}
}
