题目：
翻转一个链表
样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
挑战
在原地一次翻转完成
解题：
递归还是可以解的
java程序：
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The head of linked list.
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
// write your code here
if( head ==null || head.next ==null)
return head;
ListNode second = head.next;
head.next = null;
ListNode res = reverse(second);
second.next = head;
return res;
}
}
总耗时: 2079 ms
Python程序：
"""
Definition of ListNode class ListNode(object): def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of the linked list.
@return: You should return the head of the reversed linked list.
Reverse it in-place.
"""
def reverse(self, head):
# write your code here
if head == None or head.next == None:
return head
second = head.next;
head.next = None
res = self.reverse(second)
second.next = head
return res
总耗时: 265 ms
非递归参考于剑指OfferP113
定义三个节点：
revHead翻转后的头节点
p向前走的节点
prev要插入节点的前一个节点，同时在循环中还有一个节点pNext临时保存p的下一个节点
初始值：p=head,prev = null,revHead = null
在循环中：
先pNext = p.next 临时保存p的下一个节点，防止链表锻炼
p.next = prev p的下一个节点直线prev节点，就是翻转，链接到其前面的一个节点，为了保持每次都能这样链接
prev = p prev节点向后移动一个节点
最后p = pNext 循环下去
同时要找到链表的头节点
当pNext==null的时候 revHead = p p就是头节点,其实运行结束时候的prev节点就是指向头节点的，单独搞个头节点，看着舒服点
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The head of linked list.
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
// write your code here
ListNode revHead = null;
ListNode p = head;
ListNode prev = null;
while(p!=null){
ListNode pNext = p.next;
if(pNext == null){
// 翻转后的头节点,后面是空，结果
revHead = p;
}
// p的下一个节点指向之前要链接的节点
p.next = prev;
// 要链接的节点 直线p节点，以供下次链接
prev = p;
// p节点更新，指向pNext
p = pNext;
}
return revHead;
}
}
Java Code
总耗时: 1325 ms
"""
Definition of ListNode class ListNode(object): def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of the linked list.
@return: You should return the head of the reversed linked list.
Reverse it in-place.
"""
def reverse(self, head):
# write your code here
p = head
prev = None
revHead = None
while p!=None:
pNext = p.next
if pNext ==None:
revHead = p
p.next = prev
prev = p
p = pNext
return revHead
Python Code
总耗时: 223 ms