文档章节

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
2018/07/10
0
0
LeetCode目录。

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

Leafage_M
2017/11/21
0
0
Palindrome Linked List(leetcode234)

Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->2Output: false Example 2: Input: 1->2->2->1Output: true Follow up: Could you do it in O(n) time......

woshixin
2018/12/10
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

没有更多内容

加载失败,请刷新页面

加载更多

开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
9
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
3
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
2
0
XML

学习目标  能够说出XML的作用  能够编写XML文档声明  能够编写符合语法的XML  能够通过DTD约束编写XML文档  能够通过Schema约束编写XML文档  能够通过Dom4j解析XML文档 第1章 xm...

stars永恒
昨天
1
0
RabbitMQ学习(2)

1. 生产者客户端 void basicPublish(String exchange, String routingKey, boolean mandatory, boolean immediate, BasicProperties props, byte[] body) 1. 在生产者客户端发送消息时,首先......

江左煤郎
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部