[题目] 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分。
[要求] 如果两个链表的长度之和为N，时间复杂度要求为0(N)，额外空间复
杂度要求为0(1)
[题目]给定一个单链表的头节点head,请判断该链表是否为回文结构。
[例子] 1->2->1，返回true; 1->2- ->2- >1，返回true; 15- ->6- ->15，返回true; 1->2- >3，返回false。
[例子]如果链表长度为N，时间复杂度达到0 (N)，额外空间复杂度达到0(1)。
笔试做法：放入栈中，然后依次弹出对比，有不一样的就是回文
面试做法：（省空间）
①只把右边的放入栈中，栈只要弹空了且都想等 就是回文 ==>快慢指针
②
// n space
public static boolean isPailndrome1(Node head){
Stack<Node> stack = new Stack<>();
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;
}
// n/2 space
public static boolean isPailndrome2(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<>();
while (right != null){
stack.push(right);
right = right.next;
}
while (! stack.isEmpty()){
if (head.value != stack.pop().value){
return false;
}
head = head.next;
}
return true;
}
// o(1) space
public static boolean isPailndrome3(Node head){
if (head == null || head.next == null){
return true;
}
Node node1 = head;
Node node2 = head;
while (node1.next != null && node2.next.next != null){
node1 = node1.next;
node2 = node2.next.next;
}
//反转后半部分
node2 = node1.next;
node1.next = null;
Node node3 = null;
while (node2 != null){
node3 = node2.next;
node2.next = node1;
node1 = node2;
node2 = node3;
}
node3 = node1;
node2 = head;
boolean res = true;
while (node1 != null && node2 != null){
if (node1.value != node2.value){
return false;
}
node1 = node1.next;
node2 = node2.next;
}
//恢复
node1 = node3.next;
node3.next = null;
while (node1 != null){
node2 = node1.next;
node1.next = node3;
node3 = node1;
node1 = node2;
}
return res;
}
public static class Node{
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
[题目]给定一个单链表的头节点head,节点的值类型是整型，再给定一个整数pivot。实现- -个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
[进阶]在实现原问题功能的基础上增加如下的要求
[要求]调整后所有小于pivot的节点之间的相对顺序和调整前一样
[要求]调整后所有等于pivot的节点之间的相对顺序和调整前一样
[要求]调整后所有大于p ivot的节点之间的相对顺序和调整前一样
[要求]时间复杂度请达到0(N)，额外空间复杂度请达到0(1)。
public static Node listPartition2(Node head, int pivot){
Node sH = null;
Node sT = null;
Node eH = null;
Node eT = null;
Node mH = null;
Node mT = 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 (mH == null){
mH = head;
mT = head;
}else {
mT.next = head;
mT = head;
}
}
if (sT != null){
sT.next = eH;
eT = eT == null? sT : eT;
}
if (eT != null){
eT.next = mH;
}
}
return sH != null ? sH : (eH != null ? eH : mH);
}
[题目]一种特殊的单链表节点类描述如下
class Node{
int value;
Node next ;
Node rand ;
Node(int val) {
value = val ;
}
}
rand指针是单链表节点结构中新增的指针，rand可 能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
[要求]时间复杂度0 (N)，额外空间复杂度0(1)
//metho1 HashMap
public static Node copyListWithRand1(Node head){
HashMap<Node,Node> map = new HashMap<>();
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);
}
//metho2
public static Node copyListWithRand2(Node head){
if (head == null){
return null;
}
Node cur = head;
Node next = null;
while (cur != null){
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
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;
while (cur != null){
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return resl;
}
[题目]给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第- -个节点。如果不相交，返回nulI
[要求]如果两个链表长度之和为N，时间复杂度请达到0 (N)，额外空间复杂度请达到0(1)。
public static Node getLoopNode(Node head){
if (head == null || head.next == null || head.next.next == head){
return null;
}
Node n1 = head.next;
Node n2 = head.next.next;
while (n1 != n2){
if (n2.next == null || n2.next.next == null){
return null;
}
n1 = head.next;
n2 = head.next.next;
}
n2 = 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;//谁长谁是cur1
cur2 = cur1 == head1? head2 : head1; //谁短谁是cur2
n = Math.abs(n);
while (n != 0){
cur1 = cur1.next;
n--;
}
while (cur1 != cur2){
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
不可能相交！！！！
三种情况
//有环
public static Node bothLoop(Node head1, Node head2,Node loop1, 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;//谁长谁是cur1
cur2 = cur1 == head1? head2 : head1; //谁短谁是cur2
n = Math.abs(n);
while (n != 0){
cur1 = cur1.next;
n--;
}
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;
}
}
主函数
//方法
public static Node getNode(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,head2,loop1,loop2);
}
return null;
}