首页 > 代码库 > 234. 回文链表 Palindrome Linked List
234. 回文链表 Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
判断一个链表是否为回文串
思路:1.找到中间点,2.反转后半部分链表,3.判断前半部分与后半部分是否相同
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode nextNode = head.next;
ListNode newHead = ReverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
}
public ListNode FindMid(ListNode head) {
ListNode fast = head;
ListNode slow = head;
int num = 1;
while (fast != null) {
num++;
if (fast.next != null) {
fast = fast.next.next;
} else {
break;
}
slow = slow.next;
}
return slow;
}
public bool IsPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode midNode = FindMid(head);
ListNode newMid = ReverseList(midNode);
ListNode font = head;
ListNode back = newMid;
while (back != null) {
if (font.val != back.val) {
return false;
}
font = font.next;
back = back.next;
}
return true;
}
}
null
234. 回文链表 Palindrome Linked List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。