关于链表:一周刷完剑指offer15反转单链表

反转单链表

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 = node2
node2.next = node3
node3.next = node4
 
def printNode(head):
    result = []
    while head:
        result.append(head.values)
        head = head.next
    print(result)
printNode(node1)
newNode = reverseLink(node1)
printNode(newNode)

应用递归的实现办法：

/*python
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;
 
    }
}

如果您感觉本文有用，请点个“在看”