文档章节

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

没有更多内容

加载失败,请刷新页面

加载更多

python:关于读取文件的指定行的问题

先来造一个文件:就叫做 test.txt吧,内容是下面这个样子: 表头1,数据12,数据23,数据34,数据45,数据56,数据67,数据7 那么我们并不打算把这个表头给读出来 怎么办呢? 先来打开文...

Oh_really
6分钟前
0
0
Rails 用现代 Rails 逃离单页面应用 “兔子洞”

在工作共总是觉得turbolinks非常爽,但是却总是被说成是过时的技术,大家都喜欢spa,哪怕不用的spa的人也是禁用掉的多,找不到很好的理由劝说别人使用,这篇文章说的很到位,或者说至少是牛人...

wmzsonic
11分钟前
0
0
Hive 分布式搭建,Spark集成Hive记录

本帖详细介绍搭建步骤,仅仅记录自己搭建过程以及采坑经历。 前提环境: Hadoop集群 版本2.7.2 Spark集群 版本2.1.0 Linux版本 Centos7 准备搭建 MySql版本5.5.61 ,Hive-2.1.0 去官网下载M...

我爱春天的毛毛雨
13分钟前
0
0
打包QML程序

1、windeployqt执行路径(D:\Qt\5.12.0\msvc2017_64\bin)加入到PATH中 2、使用Qt自带的命令行交互 Command 终端(Qt 5.12.0 64-bit for Desktop (MSVC 2017))切换到 Release 编译成功的exe...

渣渣曦
51分钟前
4
0
优秀互联网高级测试工程师应该具备的能力

概述 在之前写的互联网高级测试工程师至少具备的能力一文中,提到了测试工程师至少具备的能力,但是并没有提到优秀测试工程师应该具备的能力,下文简单的谈一谈。当然这些全部都是我的个人理...

Sam哥哥聊技术
54分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部