Destructive algorithms when solving whiteboarding task

There was a discussion in comments on Stackoverflow in Russian about detecting palindrome.

Check if the linked list is a palindrome.

I give such an example for checking the linked list for palindrome (it’s leetcode #234 Palindrome Linked List):

public class Solution
{
    public bool IsPalindrome(ListNode head)
    {
        var middle = FindMiddle(head);

        var list1 = head;
        var list2 = Reverse(head, middle);

        while (list1 != middle) // or while(list2 != null)
        {
            if (list1.val != list2.val)
                return false;

            list1 = list1.next;
            list2 = list2.next;
        }

        return true;
    }

    private static ListNode FindMiddle(ListNode head)
    {
        var slow = head;
        var fast = head;

        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private static ListNode Reverse(ListNode head, ListNode last)
    {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != last)
        {
            var next = curr.next;

            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

This approach is trivial:
1. Find the middle of the list.
2. Then reverse the first half of the list.
3. And finally, check the first half and second half.

It works for O(N) time and O(1) space.

But I was told that this algorithm destroys the structure of the linked list (because of reversing). And that’s why it has limited usage in real applications. And it’s better to use a non-destructive algorithm for production code. (For this specific case: create a copy of the list, then reverse copy and compare with the original list. This will work for O(N) time and O(N) space)

Maybe, using destructive approaches is a good topic for a job interview. Would you use such code in real applications?

Also, I know one similar problem that could be solved using destructive ways.

Detecting a loop in a linked list (leetcode #141) could be solved using an additional node as a flag. Just set .next for each traversed node to flag:

public bool HasCycle(ListNode head)
{
    var flag = new ListNode(0);
    while (head != null)
    {
        if (head.next == flag)
            return true;

        var next = head.next;

        head.next = flag;

        head = next;
    }

    return false;
}

I can recommend using a classic Floyd’s Cycle Finding Algorithm instead, also known as the ‘turtle and hare’ approach.

And which problem do you know at leetcode that could be solved using destructive algorithms? What to use instead?