来源：https://leetcode.com/problems/reverse-linked-list
Reverse a singly linked list.
递归方法：递归调用直到最后一个节点再开始反转，注意保存反转后的头结点返回
Java
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) {
12 return head;
13 }
14 ListNode newHead = reverseList(head.next);
15 head.next.next = head;
16 head.next = null;
17 return newHead;
18 }
19 }
Python
1 # -*- coding:utf-8 -*-
2 # 递归
3 # class ListNode:
4 # def __init__(self, x):
5 # self.val = x
6 # self.next = None
7 class Solution:
8 # 返回ListNode
9 def ReverseList(self, pHead):
10 # write code here
11 if pHead == None or pHead.next == None:
12 return pHead
13 tmp = self.ReverseList(pHead.next)
14 pHead.next.next = pHead
15 pHead.next = None
16 return tmp
迭代方法：两个指针从头开始依次反转，注意保存下一次反转的节点指针
Java
/**
* 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 pre = head, cur = head.next, next = null;
while(cur != null) {
next = cur.next;
cur.next = pre;
if(pre == head) {
pre.next = null;
}
pre = cur;
cur = next;
}
return pre;
}
}
Python
# -*- coding:utf-8 -*-
# 迭代
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead == None or pHead.next == None:
return pHead
pre_node, cur_node = pHead, pHead.next
while pre_node and cur_node:
tmp_node = cur_node.next
cur_node.next = pre_node
pre_node = cur_node
cur_node = tmp_node
pHead.next = None
return pre_node