Reverse a single linked list

1. Topic description

Enter a linked list, reverse the list, output the new list header.

Example 2.

There is no

3

If the input header pointer is None or the entire list has only one node, the flipped list breaks and the flipped head node returned is not the end of the original list. Therefore, we need to introduce a flipped head node, and a pointer to the current node, a pointer to the node before the current node, and a pointer to the node after the current node to prevent breakage.

Recursive reverse linked list implementation, relatively easy

4. A Java implementation

A simpler non-recursive implementation:

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} * /
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // If head is empty, or if there is only one node, return directly
        if (head == null || head.next == null) {return head;
        }
        ListNode p = head;
        ListNode newHead = null; // New header node
        
        while(p ! =null){
            ListNode temp = p.next; // Save p's pointer to the next node
            p.next = newHead;
            newHead = p; // Update the header node
            p = temp;  // p = p ext, update p node
        }
        returnnewHead; }}Copy the code

Using a recursive implementation:

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} * / public class Solution {public ListNode ReverseList (ListNode head) {/ / using recursive method if (head = = null | | head. The next = = null){ return head; } ListNode headNext = ReverseList(head.next); head.next.next = head; head.next = null; return headNext; }}Copy the code

5. Python implementation

A simpler non-recursive implementation:

#! /usr/bin/env python
# -*- coding: utf-8 -*-
__title__ = "" "" '__author__ =' mike_jun '__mtime__ =' 2019-5-24 '# purpose: reverse singly linked lists "" "
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
 
Create a singly linked list
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)
Copy the code

Using a recursive implementation:

/*python public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} * / public class Solution {public ListNode ReverseList (ListNode head) {/ / using recursive method if (head = = null | | head. The next = = null){ return head; } ListNode headNext = ReverseList(head.next); head.next.next = head; head.next = null; return headNext; }}Copy the code

If you found this article useful, please click “Watching”