Created
January 13, 2025 19:06
-
-
Save davepcallan/bc0e9d706330a1ec8b4acfbc7a968a41 to your computer and use it in GitHub Desktop.
How to reverse a Linked List in C# + tests
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using Xunit; | |
public class ListNode | |
{ | |
public int Value; | |
public ListNode Next; | |
public ListNode(int value = 0, ListNode next = null) | |
{ | |
Value = value; | |
Next = next; | |
} | |
} | |
public static class LinkedListReverser | |
{ | |
/// <summary> | |
/// Reverses a singly linked list. | |
/// </summary> | |
/// <param name="head">The head node of the linked list.</param> | |
/// <returns>The new head node of the reversed linked list.</returns> | |
public static ListNode ReverseList(ListNode head) | |
{ | |
ListNode previous = null; // Tracks the previous node (initially null) | |
ListNode current = head; // Start with the head of the list | |
while (current != null) | |
{ | |
// Save the next node before breaking the link | |
ListNode nextTemp = current.Next; | |
// Reverse the current node's pointer | |
current.Next = previous; | |
// Move the pointers one step forward | |
previous = current; | |
current = nextTemp; | |
} | |
// Return the new head (previous now points to the last node) | |
return previous; | |
} | |
} | |
public class LinkedListReverserTests | |
{ | |
/// <summary> | |
/// Helper method to convert an array to a linked list. | |
/// </summary> | |
private ListNode ConvertArrayToLinkedList(int[] values) | |
{ | |
if (values == null || values.Length == 0) return null; | |
var head = new ListNode(values[0]); | |
var current = head; | |
for (int i = 1; i < values.Length; i++) | |
{ | |
current.Next = new ListNode(values[i]); | |
current = current.Next; | |
} | |
return head; | |
} | |
/// <summary> | |
/// Helper method to convert a linked list to an array. | |
/// </summary> | |
private int[] ConvertLinkedListToArray(ListNode head) | |
{ | |
var result = new System.Collections.Generic.List<int>(); | |
while (head != null) | |
{ | |
result.Add(head.Value); | |
head = head.Next; | |
} | |
return result.ToArray(); | |
} | |
[Theory] | |
[InlineData(new int[] { 1, 2, 3, 4, 5 }, new int[] { 5, 4, 3, 2, 1 })] | |
[InlineData(new int[] { 1, 2 }, new int[] { 2, 1 })] | |
[InlineData(new int[] { 1 }, new int[] { 1 })] | |
[InlineData(new int[] { }, new int[] { })] | |
public void ReverseList_ShouldReverseLinkedList(int[] input, int[] expected) | |
{ | |
// Arrange | |
var head = ConvertArrayToLinkedList(input); | |
// Act | |
var reversedHead = LinkedListReverser.ReverseList(head); | |
// Assert | |
var result = ConvertLinkedListToArray(reversedHead); | |
Assert.Equal(expected, result); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment