Skip to content

02.06. Palindrome Linked List

Description

Implement a function to check if a linked list is a palindrome.

 

Example 1: 


Input:  1->2

Output:  false

Example 2: 


Input:  1->2->2->1

Output:  true

 

Follow up:
Could you do it in O(n) time and O(1) space?

Solutions

Solution 1: Fast and Slow Pointers + Reverse List

First, we check if the list is empty. If it is, we return true directly.

Next, we use fast and slow pointers to find the midpoint of the list. If the length of the list is odd, the slow pointer points to the midpoint. If the length of the list is even, the slow pointer points to the first of the two middle nodes.

Then, we reverse the list after the slow pointer, giving us the second half of the list, with the head node as $p$.

Finally, we loop to compare the first half and the second half of the list. If there are any unequal nodes, we return false directly. Otherwise, we return true after traversing the list.

The time complexity is $O(n)$, where $n$ is the length of the list. The space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        p = slow.next
        slow.next = None
        dummy = ListNode()
        while p:
            next = p.next
            p.next = dummy.next
            dummy.next = p
            p = next
        p = dummy.next
        while p:
            if head.val != p.val:
                return False
            head = head.next
            p = p.next
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode p = slow.next;
        slow.next = null;
        ListNode dummy = new ListNode(0);
        while (p != null) {
            ListNode next = p.next;
            p.next = dummy.next;
            dummy.next = p;
            p = next;
        }
        p = dummy.next;
        while (p != null) {
            if (head.val != p.val) {
                return false;
            }
            head = head.next;
            p = p.next;
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) {
            return true;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* p = slow->next;
        slow->next = nullptr;
        ListNode* dummy = new ListNode(0);
        while (p) {
            ListNode* next = p->next;
            p->next = dummy->next;
            dummy->next = p;
            p = next;
        }
        p = dummy->next;
        while (p) {
            if (head->val != p->val) {
                return false;
            }
            head = head->next;
            p = p->next;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }
    p := slow.Next
    slow.Next = nil
    dummy := &ListNode{}
    for p != nil {
        next := p.Next
        p.Next = dummy.Next
        dummy.Next = p
        p = next
    }
    p = dummy.Next
    for p != nil {
        if head.Val != p.Val {
            return false
        }
        head = head.Next
        p = p.Next
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
    if (!head) {
        return true;
    }
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let p = slow.next;
    slow.next = null;
    const dummy = new ListNode(0);
    while (p) {
        const next = p.next;
        p.next = dummy.next;
        dummy.next = p;
        p = next;
    }
    p = dummy.next;
    while (p) {
        if (head.val !== p.val) {
            return false;
        }
        head = head.next;
        p = p.next;
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
    if (!head) {
        return true;
    }
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let p = slow.next;
    slow.next = null;
    const dummy = new ListNode(0);
    while (p) {
        const next = p.next;
        p.next = dummy.next;
        dummy.next = p;
        p = next;
    }
    p = dummy.next;
    while (p) {
        if (head.val !== p.val) {
            return false;
        }
        head = head.next;
        p = p.next;
    }
    return true;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode p = slow.next;
        slow.next = null;
        ListNode dummy = new ListNode(0);
        while (p != null) {
            ListNode next = p.next;
            p.next = dummy.next;
            dummy.next = p;
            p = next;
        }
        p = dummy.next;
        while (p != null) {
            if (head.val != p.val) {
                return false;
            }
            head = head.next;
            p = p.next;
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* public class ListNode {
*    var val: Int
*    var next: ListNode?
*    init(_ x: Int) {
*        self.val = x
*        self.next = nil
*    }
* }
*/

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if head == nil {
            return true
        }

        var slow = head
        var fast = head?.next
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }

        var p = slow?.next
        slow?.next = nil
        var dummy = ListNode(0)

        while p != nil {
            let next = p?.next
            p?.next = dummy.next
            dummy.next = p
            p = next
        }

        p = dummy.next
        var currentHead = head
        while p != nil {
            if currentHead?.val != p?.val {
                return false
            }
            currentHead = currentHead?.next
            p = p?.next
        }

        return true
    }
}

Comments