一、判断一个链表是否为回文结构
给定一个单链表的头节点head，判断该链表是否为回文结构。
【例子】
1->2->1，返回true。
1->2->2->1，返回true。
15->6->15，返回true。
1->2->3，返回false。
三种方法：可以实现O(n),O(n/2),O(1)的额外空间的算法。
//1
//需要n个额外空间 使用栈结构
public static boolean isPalindrome1(Node head){
Stack<Node> stack=new Stack<Node>();
Node cur=head;
while (cur!=null){
stack.push(cur);
cur =cur.next;
}
while (head!=null){
if (head.value!=stack.pop().value){
return false;
}
head=head.next;
}
return true;
}
//2
//需要额外空间O(n/2)
//need n/2 extra space
public static boolean isPalindrome2(Node head) {
if (head==null||head.next==null){
return true;
}
Node right = head.next;
Node cur = head;
while (cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
Stack<Node> stack = new Stack<Node>();
while (right != null) {
stack.push(right);
right = right.next;
}
while (!stack.isEmpty()) {
if (stack.pop().value != head.value) {
return false;
}
head = head.next;
}
return true;
}
通过有限几个变量来实现判断链表是否为回文结构
第一步 确定中间变量
第二步 反转右半部分链表
第三步 比较判断左右两部分值是否相等
第四步 恢复链表，返回结果
//3
//需要O(1)的额外空间复杂度
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) { // 找到中间节点
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
// n1 中点
n2 = n1.next; // n2 -> 右边部分的第一个节点
n1.next = null; // mid.next -> null
Node n3 = null;
while (n2 != null) {
n3 = n2.next; // n3 -> 保留下一个节点
n2.next = n1;
n1 = n2; // n1 move
n2 = n3; // n2 move
}
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // 判断是否为回文
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
while (n1 != null) { // 恢复原始链表
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
二、将单向链表按某值划分成左边小、中间相等、右边大的形式
给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
两种方案：利用数组或者几个有限指针变量
//方法一：利用节点数组来进行partition操作(快排重要思想) 需要开辟额外O(n)的空间
public static Node listPartition1(Node head,int pivot){
if (head==null){
return head;
}
Node cur=head;
int i=0;
while (cur!=null){
cur=cur.next;
i++;
}
Node[] nodeArr=new Node[i];
cur=head;
i=0;
for (i=0;i!=nodeArr.length;i++){
nodeArr[i]=cur;
cur = cur.next;
}
arrPartition(nodeArr,pivot);
for (i=1;i!=nodeArr.length;i++){
nodeArr[i-1].next=nodeArr[i];
}
nodeArr[i-1].next=null;
return nodeArr[0];
}
private static void arrPartition(Node[] nodeArr, int pivot) {
int small=-1;
int big=nodeArr.length;
int index=0;
while (index!=big){
if (nodeArr[index].value<pivot){
swap(nodeArr,++small,index++);
}
else if(nodeArr[index].value==pivot){
index++;
}
else {
swap(nodeArr,--big,index);
}
}
}
public static void swap(Node[] nodeArr,int a,int b){
Node tmp=nodeArr[a];
nodeArr[a]=nodeArr[b];
nodeArr[b]=tmp;
}
//方法二：利用有限几个变量实现 额外空间O(1)
//在原来链表的基础上，用六个节点变量把链表按要求的分为三小段，最后再连起来
public static Node listPartition2(Node head,int pivot) {
Node sH=null;
Node sT=null;
Node eH=null;
Node eT=null;
Node bH=null;
Node bT=null;
Node next=null;
while (head!=null) {
next=head.next;
head.next=null;
if (head.value<pivot){
if (sH==null){
sH=head;
sT=head;
}else {
sT.next=head;
sT=head;
}
}
else if (head.value==pivot){
if (eH==null){
eH=head;
eT=head;
}else {
eT.next=head;
eT=head;
}
}
else {
if (bH==null) {
bH=head;
bT=head;
}else {
bT.next=head;
bT=head;
}
}
head=next;
}
if (sT!=null){
sT.next=eH;
eT=eT==null?sT:eT;
}
if (eT!=null){
eT.next=bH;
}
return sH!=null?sH:eH!=null?eH:bH;
}
三、复制含有随机指针节点的链表
一种特殊的单链表节点类描述如下
class Node{
int value;
Node next;
Node rand;
Node(int val){
value=val;
} }
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
两种方法：
一种是直接用hash表，根据键值对的关系来实现链表的复制。
额外空间复杂度为O(n)
一种是通过在链表的每一个节点后复制相同节点，然后再实现rand指针的复制，最后将链表分离出来。额外空间复杂度O(1)
一、hashmap实现
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.value));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
二、复制每一个节点实现
public static Node copyListWithRand2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// copy node and link to every node
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
// set copy node rand
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// split
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
四、两个单链表相交的一系列问题
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
两个链表长度之和为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
这个题目需要从两个链表有环或无环两个方面进行分析。
一、两链表都无环
两个链表无环返回相交值分为两种情况，一种是两链表无交点，另外一种是两链表有一个焦点，其他情况不存在。
二、两链表都有环
两个链表无环返回相交值分为三种情况，第一种是两链表都有环但互不相交，第二种是两链表都有环且入环节点相同，第三种是两链表都有环但入环节点不同。
public class FindFirstIntersectNode {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node getIntersectNode(Node head1, Node head2) {//返回相交节点总方法
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}
public static Node getLoopNode(Node head) {//判断链表是否有环
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next; // n1 -> slow
Node n2 = head.next.next; // n2 -> fast
while (n1 != n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // n2 -> walk again from head
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
public static Node noLoop(Node head1, Node head2) {//两链表无环判断相交节点
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {//两链表有环判断相交节点
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
部分题目来源Leecode