反转单链表

1. 题目形容

输出一个链表，反转链表后，输入新链表的表头。

2. 示例

无

3. 解题思路

输出的链表头指针为None或者整个链表只有一个结点时，反转后的链表呈现断裂，返回的翻转之后的头节点不是原始链表的尾结点。因而须要引入一个翻转后的头结点，以及一个指向以后结点的指针，一个指向以后结点前一个结点的指针，一个指向以后结点后一个结点的指针，防止出现断裂。

递归反转链表实现，绝对比拟容易一些

4. Java实现

比较简单的非递归的实现办法：
/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode ReverseList(ListNode head) {        // 如果是head为空，或者只有一个节点，则间接返回        if (head == null || head.next == null){            return head;        }        ListNode p = head;        ListNode newHead = null; // 新的头节点                while(p != null){            ListNode temp = p.next; // 保留p指向下一个节点的指针            p.next = newHead;            newHead = p; // 更新头节点            p = temp;  // 即 p = p.next ，更新p节点        }        return newHead;            }}
应用递归的实现办法：
/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode ReverseList(ListNode head) {        // 应用递归的办法        if (head == null || head.next == null){            return head;        }        ListNode headNext = ReverseList(head.next);        head.next.next = head;        head.next = null;        return headNext;     }}

5. Python实现

比较简单的非递归的实现办法：
#!/usr/bin/env python# -*- coding: utf-8 -*-"""__title__ = ''__author__ = 'mike_jun'__mtime__ = '2019-5-24'#目标： 反转单链表"""def reverseLink(head):    #pass    if not head or not head.next:        return head    p = head    newHead = None    while p:        temp = p.next        p.next = newHead        newHead = p        p = temp    return newHead #创立一个单链表class Node():    def __init__(self, values):        self.next = None        self.values = values node1 = Node(1)node2 = Node(2)node3 = Node(3)node4 = Node(4)node1.next = node2node2.next = node3node3.next = node4 def printNode(head):    result = []    while head:        result.append(head.values)        head = head.next    print(result)printNode(node1)newNode = reverseLink(node1)printNode(newNode)
应用递归的实现办法：
/*pythonpublic class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode ReverseList(ListNode head) {        // 应用递归的办法        if (head == null || head.next == null){            return head;        }        ListNode headNext = ReverseList(head.next);        head.next.next = head;        head.next = null;        return headNext;     }}
如果您感觉本文有用，请点个“在看”