醉了：算法题，不能丢啊，不能丢啊，吗的，我怎么觉得我越来越傻！！！

题目：单链表反转

单链表的概念熟记于心

class Node<K>{    //真尴尬，java范型写的太少了
 
                private K val;
 
                public Node<K> next; 
 
}

class Node(object): #python版
 
               def __init__(val,next):
 
                     self.val = val
 
                     self.next = next

特点：

a、头引用或者头结点指向第一个结点，然后最后一个结点指向null或None（Python中的null）

0、java解法（两种解法）

参考文章：https://www.cnblogs.com/keeya/p/9218352.html

两个思路：

a、从第一个结点一直向后开始变更引用 （从前往后）

b、从后面最后一个结点向前开始变更引用（递归）（从后往前）

//第一种解法，从第一个结点，一直向右，直到最后一个结点
 
    private static Node reverseList(Node head) {
        Node pre = null;
        Node next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
 
…………代码语句执行过程分析…………
 
语句执行，pre赋值为null
 
语句执行，next赋值为null
 
第一轮循环，参与的是 1号、2号结点， 局部变量next先指向2号结点，1号结点的next指向null，最终当前的pre结点为1号结点，head赋值为2号结点
 
第二轮循环，参与的是 2号、3号结点， 局部变量next先指向3号结点，2号结点next指向1号结点，最终当前的pre结点为2号结点，head赋值为3号结点
 
第三轮循环，参与的是 3号结点、null结点， 局部变量next先指向null，3号结点next指向2号结点，最终当前的pre结点为3号结点，head被赋值为null
 
第四轮循环，head为null，循环结束
 
语句执行，返回pre，此时pre的值是3号结点

//第二种解法   
 
 private static Node reverseListBySelf(Node head) {
        if (head == null || head.next == null)
            return head;
        Node temp = head.next;
        Node newHead = reverseListBySelf(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }
 
 
…………方法调用栈过程…………
 
第三次reverseListBySelf，传入结点为3号结点
语句执行，if判断为true，因为3号结点的next为null
语句执行，return传入的3号结点
 
 
 
第二次reverseListBySelf，传入结点为2号结点
语句执行，if判断为false
语句执行，temp为3号结点
语句执行，newHead，再去执行reverseListBySelf方法，传入的是3号结点，等待newHead指向3号结点
语句执行，temp3号结点next指向2号结点
语句执行，当前head2号结点的next指向到了null
语句执行，return newHead为3号结点
 
 
第一次reverseListBySelf，传入结点为1号结点
语句执行，if判断为false
语句执行，temp为2号结点
语句执行，newHead，去执行reverseListBySelf方法，传入的是2号结点，newHead拿到了第二次的返回值了，newHead同样指向3号结点
语句执行，2号结点指向1号结点
语句执行，1号结点指向null
语句执行，return newHead为3号结点
 
 
main方法开始
 
 
 

1、python解法（用到连续赋值）

假如要对一个链表进行翻转，就比如把1—>2->3->4转化为4->3->2->1

对于这个问题很简单，只要反转指针就可以了，假如链表结构为：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

我们可以用很简单的三行代码完成这个过程：

def reverseList(self, head):
        L = ListNode(float("-inf"))
        while head:
            L.next, head.next, head = head, L.next, head.next
        return L.next