5.15 - Stacks and Queues-白红宇

5.15 - Stacks and Queues

阅读量：5796 次

发布时间：2019-06-18

本文共 2085 字，大约阅读时间需要 6 分钟。

Solution1: Reverse and Compare

翻转整个Linked List, 然后用两个指针进行逐一比对

Solution2: Iterative Approach -> use Stack

boolean isPalindrome(ListNode head) {    ListNode fast = head;    ListNode slow = head;        Stack
    
      stack = new Stack
     
      ();    while (fast != null && fast.next != null) {        stack.push(slow.data);        slow = slow.next;        fast = fast.next.next;    }// Has odd number of elements, so skip the middle element     if (fast != null) {        slow = slow.next;    }    while (slow != null) {        int top = stack.pop().intValue();        /* If values are different, then it's not a palindrome */        if (top != slow.data) {            return false;        }        slow = slow.next;    }    return true;}

```

Recursive Approach

Q: How recursive function would work?

Q: How can we get to the end of the list? How can we compare node i with node n - i?

从head 开始遍历，但是从中间开始做compare

class Result {    public ListNode node;    public boolean result;}/* Result当中 {    node 存储的是当前遍历的指针位置        result表示当前比较的结果 }*/boolean isPalindrome(ListNode head) {    int length = getLength(head);    Result p = isPalindromeRecurse(head, length);    return p.result;}Result isPalindromeRecurse(ListNode head, int length) {        // 递归的出口     if (head == null || length <= 0) {         //if the input is null  or the head points to the middle of the list        return new Result(head, true);    } else if (length == 1) {         // if the middle + 1 of the list          return new Result(head.next, true);    }        // 递归的调用    Result res = isPalindromeRecurse(head.next, length - 2);    if (!res.result || res.node == null) {        return res;    }    // result    res.result = (head.data == res.node.data);    /* Return corresponding node. */    //在递归出口之前 将指针右移    res.node = res.node.next;        return res;}