-2c57ec47146f40cbabf9adc9f224a0a3.jpg)
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/** 果不其然的超时间了，
*/
public boolean isPalindrome(ListNode head) {
ListNode self=head;
ListNode reversalNode=reversal(head);
while(self!=null&&reversalNode!=null){
if(self.val!=reversalNode.val){
return false;
}
}
return true;
}
public ListNode reversal(ListNode head){
ListNode a=head,b=null;
while(a!=null){
//记录a的后继节点
ListNode c=a.next;
//解绑a节点
a.next=b;
//在b指针绑定上解绑带来的a节点
b=a;
//把曾经记下的a的后继节点，还给a，用于下次的迭代。
a=c;
}
return b;
}
改进版本，翻转一半进行比较 使用快慢指针
public boolean isPalindrome(ListNode head) {
if(head==null){
return true;
}
ListNode self=head;
ListNode reversalNode=reversal(getTailNode(head));
while(self!=null&&reversalNode!=null){
if(self.val!=reversalNode.val){
return false;
}
self=self.next;
reversalNode=reversalNode.next;
}
return true;
}
public ListNode reversal(ListNode head){
ListNode a=head,b=null;
while(a!=null){
//记录a的后继节点
ListNode c=a.next;
//解绑a节点
a.next=b;
//在b指针绑定上解绑带来的a节点
b=a;
//把曾经记下的a的后继节点，还给a，用于下次的迭代。
a=c;
}
return b;
}
public ListNode getTailNode(ListNode head){
ListNode fast=head,slow=head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
/**
*还可以遍历链表，然后把数据放在数组中，然后使用首尾双指针比对
*/
public boolean isPalindrome(ListNode s) {
if (s == null) return true;
ListNode head=s,head1=s;
int leng=0;
while(head!=null){
leng++;
head=head.next;
}
int i=0,j=0;
int[] a=new int[leng];
while(head1!=null){
a[i++]=head1.val;
head1=head1.next;
}
int k=i-1;
while (j<k){
if (a[j]!=a[k]){
return false;
}
j++;
k--;
}
return true;
}
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
*反转列表，1->2->3->4->5 -》 5->4->3->2->1
*首先我需要去遍历当前的链表，采取迭代法
* 利用c记录头节点的后缀，b作为结果，用a去进行迭代。通过交换a的值，最终当遍历完毕，
* b就是反转后的列表
*/
public ListNode reverseList(ListNode head) {
ListNode a=head,b=null,c;
while(a!=null){
c= a.next;
a.next=b;
b=a;
a=c;
}
return b;
}
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
/**
* 采取快慢指针来迭代删除。
* 参照两数相加的链表操作，使用辅助链表(哨兵)
* 根据题意我们知道要删除倒数第N个，所以快慢指针的初始步长差就是N，由于使用辅助列表所以相差为N+1；
* 直到快指针走完，那么删除慢指针的下一个就是删除了倒数第N个。
* @param head
* @param n
* @return
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode result=new ListNode(0);
result.next=head;
ListNode start=result;
ListNode end=result;
int i=0;
//直到N指针走完了
while(start!=null){
if(i<n+1){
i++;
//计算N指针
start=start.next;
}else{
start=start.next;
end=end.next;
}
}
//删除这个下一个节点
end.next=end.next.next;
//返回原链
return result.next;
}
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
/**
* 合并俩个有序链表
* 输入：1->2->4, 1->3->4
* 输出：1->1->2->3->4->4
* 参照归并排序的算法。
* 当 l1,l2不为空的时候，遍历全部，
* 如果l1遍历完了那么直接把l2的后续部分添加在结果后面。同理l2走完了 l1也是一样加载结果后面
* 关键在于比较l2和l1节点的值
* l1.val>=l2.val
* :更新结果为l2节点，同时把l2=l2.next。然后更新结果r=r.next;
* l1.val<l2.val
* :更新结果为l1节点，同时把l1=l1.next。然后更新结果r=r.next;
* 遍历全部完毕之后，输出原始指针的后继。即新链表
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode r=new ListNode(0);
ListNode ret=r;
while(l1!=null||l2!=null){
if(l1==null){
ListNode x=l2.next;
l2.next=null;
r.next=l2;
l2=x;
}else if(l2==null){
ListNode x=l1.next;
l1.next=null;
r.next=l1;
l1=x;
}else if(l1.val>=l2.val){
ListNode x=l2.next;
l2.next=null;
r.next=l2;
l2=x;
}else{
ListNode x=l1.next;
l1.next=null;
r.next=l1;
l1=x;
}
r=r.next;
}
return ret.next;
}