文档章节

Palindrome Linked List

zhuguorong
 zhuguorong
发布于 2016/08/07 20:51
字数 301
阅读 2
收藏 0

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;
		   }
	 }

 

© 著作权归作者所有

共有 人打赏支持
zhuguorong
粉丝 0
博文 5
码字总数 663
作品 0
杭州
LeetCode:Palindrome Linked List - 回文链表

1、题目名称 Palindrome Linked List(回文链表) 2、题目地址 https://leetcode.com/problems/palindrome-linked-list/ 3、题目内容 英文:Given a singly linked list, determine if it i......

北风其凉
2015/12/18
196
0
234. Palindrome Linked List - LeetCode

Question 234. Palindrome Linked List Solution 题目大意:给一个链表,判断是该链表中的元素组成的串是否回文 思路:遍历链表添加到一个list中,再遍历list的一半判断对称元素是否相等,注...

yysue
07/10
0
0
LeetCode目录。

按照LeetCode的Tags来区分的话,目前共有34个Tag,只列出已经解决的题,各分类中按照题目编号排序: Linked List。 Solved:21/28 Array。

Leafage_M
2017/11/21
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0
决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
01/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
7分钟前
0
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
41分钟前
0
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
0
0
openJDK之sun.misc.Unsafe类CAS底层实现

注:这篇文章参考了https://www.cnblogs.com/snowater/p/8303698.html 1.sun.misc.Unsafe中CAS方法 在sun.misc.Unsafe中CAS方法如下: compareAndSwapObject(java.lang.Object arg0, long a......

汉斯-冯-拉特
今天
2
0
设计模式之五 责任链模式(Chain of Responsibility)

一. 场景 相信我们都有过这样的经历; 我们去职能部门办理一个事情,先去了A部门,到了地方被告知这件事情由B部门处理; 当我们到了B部门的时候,又被告知这件事情已经移交给了C部门处理; ...

JackieRiver
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部