In-place Reversal of a LinkedList
Karambir Sharma
Full Stack Developer at Allstate | Competitive Programming | System Design | DataStructure and Algo | Azure | Azure Cloud Certified| AWS
I'm going to cover all the LeetCode Patterns for coding Interviews mentioned by a few folks. I'll write the code using C#. Today's post is related to In-place Reversal of a LinkedList. If anyone sees any area of improvement please feel free to add.
To reverse a LinkedList, we need to reverse one node at a time. We will start with a pointer current which will initially point to the head of the LinkedList and a pointer previous which will point to the previous node that we have to process. Initially previous will be pointed to null.
We will reverse the head node by pointing it to the previous before moving on to the next node. Also, we will update the previous to always point to the previous node that we have processed.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LeetCodePattren
{
internal class InPlaceReversalLinkedList
{
public class Node
{
public Node next;
public int val;
public Node(int val)
{
this.val = val;
this.next = null;
}
}
public Node ReverseLinkedListInPlace(Node head)
{
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
//current pointer point out to head
Node current = head;
领英推荐
// in starting previous node is null
Node previous = null;
while (current != null)
{
// moving current node to next
current=head.next;
//pointing head to previous node
head.next = previous;
// moving previous to head
previous = head;
// moving head to current
head = current;
}
return previous;
}
public static void Main(string[] args)
{
Node node=new Node(5);
node.next = new Node(9);
node.next.next = new Node(10);
node.next.next.next = new Node(11);
node.next.next.next.next= new Node(12);
InPlaceReversalLinkedList inPlaceReversalLinkedList = new InPlaceReversalLinkedList();
Node node1 =inPlaceReversalLinkedList.ReverseLinkedListInPlace(node);
while (node1 != null) {
Console.WriteLine(node1.val);
node1=node1.next;
}
Console.ReadLine();
}
}
}