Palindrome Linked List
Palindrome Linked List
zhuguorong 发表于2年前
Palindrome Linked List
  • 发表于 2年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

Given a singly linked list, determine if it is a palindrome.

/*
 * Given a singly linked list, determine if it is a palindrome.
 * 
 * 
 * This can be solved by reversing the 2nd half and compare the two halves. Let's start with an example [1, 1, 2, 1].

In the beginning, set two pointers fast and slow starting at the head.

1 -> 1 -> 2 -> 1 -> null 
sf
(1) Move: fast pointer goes to the end, and slow goes to the middle.

1 -> 1 -> 2 -> 1 -> null 
          s          f
(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

1 -> 1    null <- 2 <- 1           
h                      s
(3) Compare: run the two pointers head and slow together and compare.

1 -> 1    null <- 2 <- 1             
     h            s
In this end, check if slow == null. For this example, since slow != null, return false.
 * */
public class Solution {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	public boolean isPalindrome(ListNode head) {
		 ListNode fast = head;
		 ListNode slow = head;
		 while(fast!=null&&fast.next!=null)
		 {
			 fast = fast.next.next;
			 slow = slow.next;
		 }
		 if(fast!=null)//当节点个数为奇数个的时候
			 slow = slow.next;
		 
		 //把slow反转
		 slow = reverseList(slow);
		 
		 //再与头开始的节点进行比较
		 //此时slow节点的个数小于等于头节点的个数
		 while(slow!=null&&slow.val==head.val)
		 {
			 slow = slow.next;
			 head = head.next;
		 }
		 return slow == null;//当slow为null时说明 上一个while中都成立,否则就说明有节点不相等
		 
    }
	public ListNode reverseList(ListNode head) {
        ListNode newhead = null;
        while(head!=null)
        {
        	ListNode next = head.next;
        	head.next = newhead;
        	newhead = head;
        	head = next;
        }
        return newhead;
    }
}
 class ListNode {
	   int val;
	   ListNode next;
	   ListNode(int x) 
	   { 
		   val = x;
		   }
	 }

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 5
码字总数 663
×
zhuguorong
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: