FastPrep
Problem · Linked List

Palindrome Linked List with Restoration

Learn this problem
● MediumMicrosoft logoMicrosoftFULLTIMEONSITE INTERVIEW
See Microsoft hiring insights

Problem statement

Given the head of a non-empty singly linked list, determine whether its values form a palindrome while using constant auxiliary space for the comparison.

Reverse the second half in place, compare the two halves, and restore the list before returning. Return an integer array whose first value is 1 when the list is a palindrome and 0 otherwise; the remaining values must be the restored list from head to tail.

Function

checkAndRestorePalindrome(head: ListNode) → int[]

Examples

Example 1

head = [1,2,2,1]return = [1,1,2,2,1]

The values are palindromic, and the returned suffix proves that the original order was restored.

Example 2

head = [1,2,3]return = [0,1,2,3]

The end values differ, but the list still appears in its original order after the check.

Constraints

  • The list contains at least one node.
  • Every node value is a signed integer.
  • The list is acyclic.

More Microsoft problems

drafts saved locally
public int[] checkAndRestorePalindrome(ListNode head) {
    // TODO: check the palindrome and restore the linked list.
}
head[1,2,2,1]
expected[1,1,2,2,1]
checking account