|
判断是否是回文链表：
public static class Node{
? ? public int value;
? ? public Node next;
? ? public Node(int data){
? ? ? ? this.value = data;
? ? }
}
//需要n的额外空间：
public static boolean isPalindrome1(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;
}
//需要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){//find mid node,利用快慢指针
? ? ? ? n1 = n1.next;//n1->mid
? ? ? ? n2 = n2.next.next;//n2->end
? ? }
? ? n2 = n1.next;
? ? n1.next = null;
? ? Node n3 = null;
? ? while (n2 != null){//反转右部分的链表
? ? ? ? n3 = n2.next;
? ? ? ? n2.next = n1;
? ? ? ? n1 = n2;
? ? ? ? n2 = n3;
? ? }
? ? 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;
}
判断两链表在哪个节点相交：遍历两链表得到长度lens1和lens2，得到两者差值，再让长的那个先走差值步，再一起走，内存地址相等的节点即为相交节点
判断链表是否有环：若指针能指到null，则无环
判断链表入环节点是哪一个：先让快指针从node.next.next开始行走，慢指针从node.next开始行走，快的一次走两步，慢的一次走一步，在他们在环内相遇时，将快指针指向头结点，再与慢指针一起一次走一步，直到他们再次相遇，指向的节点为入环节点
|