09、回文链表

题目描述

回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

数组法

题目解析

题目理解起来很简单，判断是否为回文，如果单纯判断一个字符串或者数组是不是回文很容易。因为数组查询元素的时间复杂度为 O(1)，但是链表的查询时间复杂度为 O(n)，而且题目中的链表为单链表，指针只能后移不能前移。所以我们判断起来会比较困难。

巧用数组法：

我们首先将链表的所有元素都保存在数组中，然后再利用双指针遍历数组，进而来判断是否为回文。这个方法很容易理解，而且代码实现也比较简单。

代码

Java Code:

class Solution {
    public boolean isPalindrome(ListNode head) {
        //这里需要用动态数组，因为我们不知道链表的长度
        List<Integer> arr = new ArrayList<Integer>();
        ListNode copynode = head;
        //将链表的值复制到数组中
        while (copynode != null) {
            arr.add(copynode.val);
            copynode = copynode.next;
        }
        //双指针遍历数组
        int back = 0;
        int pro = arr.size() - 1;
        while (back < pro) {
            //判断两个指针的值是否相等
            if (!arr.get(pro).equals(arr.get(back))) {
                return false;
            }
            //移动指针
            back++;
            pro--;
        }
        return true;
    }
}

C++ Code:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //这里需要用动态数组，因为我们不知道链表的长度
        vector<int> arr;
        ListNode* copynode = head;
        //将链表的值复制到数组中
        while (copynode) {
            arr.push_back(copynode->val);
            copynode = copynode->next;
        }
        //双指针遍历数组
        int back = 0;
        int pro = arr.size() - 1;
        while (back < pro) {
            //判断两个指针的值是否相等
            if (arr[back] != arr[pro]) {
                return false;
            }
            //移动指针
            back++;
            pro--;
        }
        return true;
    }
};

JS Code:

var isPalindrome = function (head) {
  let arr = [];
  let copynode = head;
  //将链表的值复制到数组中
  while (copynode) {
    arr.push(copynode.val);
    copynode = copynode.next;
  }
  //双指针遍历数组
  let back = 0;
  let pro = arr.length - 1;
  while (back < pro) {
    //判断两个指针的值是否相等
    if (arr[back] !== arr[pro]) {
      return false;
    }
    //移动指针
    back += 1;
    pro -= 1;
  }
  return true;
};

Python Code:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        arr = []
        copynode = head
        # 将链表的值复制到数组中
        while copynode is not None:
            arr.append(copynode.val)
            copynode = copynode.next
        # 双指针遍历数组
        back = 0
        pro = len(arr) - 1
        while back < pro:
        	# 判断两个指针的值是否相等
            if arr[back] != arr[pro]:
                return False
            # 移动指针
            back += 1
            pro -= 1
        return True

Swift Code：

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        // 这里需要用动态数组，因为我们不知道链表的长度
        var arr:[Int?] = []
        var copynode = head
        // 将链表的值复制到数组中
        while copynode != nil {
            arr.append(copynode?.val)
            copynode = copynode?.next
        }
        // 双指针遍历数组
        var back = 0, pro = arr.count - 1
        while back < pro {
            // 判断两个指针的值是否相等
            if arr[pro] != arr[back] {
                return false
            }
            // 移动指针
            back += 1
            pro -= 1
        }
        return true
    }
}

Go Code:

func isPalindrome(head *ListNode) bool {
    // 将节点中的值按顺序放在arr中。
    arr := []int{}
    node := head
    for node != nil {
        arr = append(arr, node.Val)
        node = node.Next
    }
    // 双指针判断是否为回文
    l, r := 0, len(arr) - 1
    for l < r {
        if arr[l] != arr[r] {
            return false
        }
        l++
        r--
    }
    return true
}

这个方法可以直接通过，但是这个方法需要辅助数组，那我们还有其他更好的方法吗？

双指针翻转链表法

题目解析

在上个题目中我们知道了如何找到链表的中间节点，那我们可以在找到中间节点之后，对后半部分进行翻转，翻转之后，重新遍历前半部分和后半部分进行判断是否为回文。

动图解析：

img

代码

Java Code：

class Solution {
    public boolean isPalindrome(ListNode head) {
         if (head==null || head.next==null) {
             return true;
         }
         //找到中间节点，也就是翻转的头节点,这个在昨天的题目中讲到
         //但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
         ListNode midnode = searchmidnode(head);
         //原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
         //这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
         ListNode backhalf = reverse(midnode.next);
         //遍历两部分链表，判断值是否相等
         ListNode p1 = head;
         ListNode p2 = backhalf;
         while (p2 != null) {
            if (p1.val != p2.val) {
                //若要还原，记得这里也要reverse
                midnode.next = reverse(backhalf);
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        //还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
        //当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
        midnode.next = reverse(backhalf);
        return true;
    }
    //找到中点
    public ListNode searchmidnode (ListNode head) {
          ListNode fast = head;
          ListNode slow = head;
          while (fast.next != null && fast.next.next != null) {
              fast = fast.next.next;
              slow = slow.next;
          }
          return slow;
    }
    //翻转链表
    public ListNode reverse (ListNode slow) {
          ListNode low  = null;
          ListNode temp = null;
          while (slow != null) {
              temp = slow.next;
              slow.next = low;
              low = slow;
              slow = temp;
          }
          return low;
    }
}

C++ Code：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
              return true;
         }
         //找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
         //但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
         ListNode * midnode = searchmidnode(head);
         //原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
         //这里我们用的是midnode->next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
         ListNode * backhalf = reverse(midnode->next);
         //遍历两部分链表，判断值是否相等
         ListNode * p1 = head;
         ListNode * p2 = backhalf;
         while (p2 != nullptr) {
            if (p1->val != p2->val) {
                //若要还原，记得这里也要reverse
                midnode->next = reverse(backhalf);
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        //还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
        //当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
        midnode->next = reverse(backhalf);
        return true;
    }
    //找到中间的部分
    ListNode * searchmidnode (ListNode * head) {
          ListNode * fast = head;
          ListNode * slow = head;
          while (fast->next != nullptr && fast->next->next != nullptr) {
              fast = fast->next->next;
              slow = slow->next;
          }
          return slow;
    }
    //翻转链表
    ListNode * reverse (ListNode * slow) {
          ListNode * low  = nullptr;
          ListNode * temp = nullptr;
          while (slow != nullptr) {
              temp = slow->next;
              slow->next = low;
              low = slow;
              slow = temp;
          }
          return low;
    }
};

JS Code:

var isPalindrome = function (head) {
  if (head === null || head.next === null) {
    return true;
  }
  //找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
  //但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
  let midnode = searchmidnode(head);
  //原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
  //这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
  let backhalf = reverse(midnode.next);
  //遍历两部分链表，判断值是否相等
  let p1 = head;
  let p2 = backhalf;
  while (p2 != null) {
    if (p1.val != p2.val) {
      //若要还原，记得这里也要reverse
      midnode.next = reverse(backhalf);
      return false;
    }
    p1 = p1.next;
    p2 = p2.next;
  }
  //还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
  //当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
  midnode.next = reverse(backhalf);
  return true;
};

//找到中点
var searchmidnode = function (head) {
  let fast = head;
  let slow = head;
  while (fast.next != null && fast.next.next != null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
};

//翻转链表
var reverse = function (slow) {
  let low = null;
  let temp = null;
  while (slow != null) {
    temp = slow.next;
    slow.next = low;
    low = slow;
    slow = temp;
  }
  return low;
};

Python Code:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return True
        # 找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
        # 但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
        midnode = self.searchmidnode(head)
        # 原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
        # 这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
        backhalf = self.reverse(midnode.next)
        # 遍历两部分链表，判断值是否相等
        p1 = head
        p2 = backhalf
        while p2 is not None:
            if p1.val != p2.val:
                # 若要还原，记得这里也要reverse
                midnode.next = self.reverse(backhalf)
                return False
            p1 = p1.next
            p2 = p2.next
        # 还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
        # 当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
        midnode.next = self.reverse(backhalf)
        return True

    # 找到中点
    def searchmidnode(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    # 翻转链表
    def reverse(self, slow):
        low = None
        temp = None
        while slow is not None:
            temp = slow.next
            slow.next = low
            low = slow
            slow = temp
        return low

Swift Code：

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if head == nil || head?.next == nil {
            return true
        }
        //找到中间节点，也就是翻转的头节点,这个在昨天的题目中讲到
        //但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
        var midnode = searchmidnode(head)
        //原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
        //这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
        var backhalf = reverse(midnode?.next);
        //遍历两部分链表，判断值是否相等
        var p1 = head
        var p2 = backhalf
        while p2 != nil {
            if p1?.val != p2?.val {
                midnode?.next = reverse(backhalf)
                return false
            }
            p1 = p1?.next
            p2 = p2?.next
        }
        //还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
        //当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
        midnode?.next = reverse(backhalf)
        return true
    }
    //找到中点
    func searchmidnode(_ head: ListNode?) -> ListNode? {
        var fast = head, slow = head
        while fast?.next != nil && fast?.next?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
        }
        return slow
    }
    //翻转链表
    func reverse(_ slow: ListNode?) -> ListNode? {
        var slow = slow
        var low: ListNode?
        var temp: ListNode?
        while slow != nil {
            temp = slow?.next
            slow?.next = low
            low = slow
            slow = temp
        }
        return low
    }
}

Go Code:

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    midNode := searchMidNode(head)
    backHalf := reverse(midNode.Next)

    // 判断左右两边是否一样（回文）
    p1, p2 := head, backHalf
    for p2 != nil {
        if p1.Val != p2.Val {
            midNode.Next = reverse(backHalf)
            return false
        }
        p1 = p1.Next
        p2 = p2.Next
    }
    // 不破坏原来的数据
    midNode.Next = reverse(backHalf)
    return true
}

// searchMidNode 求中间的节点
func searchMidNode(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

// reverse 反转链表
func reverse(node *ListNode) *ListNode {
    var pre *ListNode
    for node != nil {
        nxt := node.Next
        node.Next = pre
        pre = node
        node = nxt
    }
    return pre
}