206. Reverse Linked List

leetcode easy

#csharp#easy#leetcode#linked-list

Task

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

C# solution

matched/original

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
public:
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

Java solution

matched/original

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

JavaScript solution

matched/original

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

class Solution {
    reverseList(head) {
        let prev = null;
        let curr = head;
        while (curr !== null) {
            let nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

Python solution

matched/original

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        return prev

Go solution

matched/original

package main

type ListNode struct {
    val  int
    next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil
    curr := head
    for curr != nil {
        nextTemp := curr.next
        curr.next = prev
        prev = curr
        curr = nextTemp
    }
    return prev
}

func main() {
}

Explanation

Algorithm

1️⃣

Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.

2️⃣

Пройдитесь по списку с помощью цикла:

Сохраните ссылку на следующий узел curr в переменную nextTemp.

Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.

Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.

3️⃣

После завершения цикла верните prev как новую голову развернутого списка.

😎