LeetCode每日一题-1：反转链表

class Solution {
 public ListNode reverseList(ListNode head) {
  //申请结点，pre和 cur，pre指向null
  ListNode pre = null;
  ListNode cur = head;
  ListNode tmp = null;
  while(cur!=null) {
   //记录当前节点的下一个节点
   tmp = cur.next;
   //然后将当前节点指向pre
   cur.next = pre;
   //pre和cur节点都前进一位
   pre = cur;
   cur = tmp;
  }
  return pre;
 }
}

class Solution(object):
    def reverseList(self, head):
        if not head or not head.next:
            return head
        l = head 
        r = head.next 
        remain = r.next 
        l.next = None
        while r:
            r.next = l 
            l = r 
            r = remain 
            if remain:
                remain = remain.next
        return l

class Solution {
 public ListNode reverseList(ListNode head) {
  //递归终止条件是当前为空，或者下一个节点为空
  if(head==null || head.next==null) {
   return head;
  }
  //这里的cur就是最后一个节点
  ListNode cur = reverseList(head.next);
  //如果链表是 1->2->3->4->5，那么此时的cur就是5
  //而head是4，head的下一个是5，下下一个是空
  //所以head.next.next 就是5->4
  head.next.next = head;
  //防止链表循环，需要将head.next设置为空
  head.next = null;
  //每层递归函数都返回cur，也就是最后一个节点
  return cur;
 }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or head.next == None: return head
        res = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return res