链表经典算法题
1.快慢指针
1)输入链表头节点，奇数长度返回中点，偶数长度返回上中点
class Node{
public int value;
public Node next;
public Node(int value) {
this.value = value;
next = null;
}
public static Node midOrUpMidNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
Node fast = head;
Node slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
2)输入链表头节点，奇数长度返回中点，偶数长度返回下中点
public static Node midOrDownMidNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
Node fast = head;
Node slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return fast.next == null ? slow : slow.next;
}
3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
public static Node midOrUpMidPreNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
Node fast = head;
Node slow = head;
Node cur = null;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
cur = slow;
slow = slow.next;
}
return cur;
}
4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
public static Node midOrDownMidPreNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
Node fast = head;
Node slow = head;
Node cur = null;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
cur = slow;
slow = slow.next;
}
return fast.next == null ? cur : slow;
}
2.给定一个单链表的头节点head，请判断该链表是否为回文结构
1)栈方法特别简单（笔试用)
public static boolean isPalindrome1(Node head) {
if (head == null || head.next == null) {
return true;
}
Stack<Node> stack = new Stack<>();
Node node = head;
while (node != null) {
stack.push(node);
node = node.next;
}
node = head;
while (!stack.isEmpty()) {
if (node.value != stack.pop().value) {
return false;
}
node = node.next;
}
return true;
}
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 (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
2)改原链表的方法就需要注意边界了（面试用)
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node fast = head;
Node slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
Node pre = null;
Node curr = slow.next;
slow.next = null;
Node next = null;
while (curr != null) {
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
Node node = pre;
Node n1 = head;
while (n1 != null && pre != null) {
if (n1.value != pre.value) {
return false;
}
n1 = n1.next;
pre = pre.next;
}
pre = null;
curr = node;
next = null;
while (curr != null) {
next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return true;
}
3.将单向链表按某值划分成左边小、中间相等、右边大的形式
1)把链表放入数组里，在数组上做partition(笔试用)
public static Node listPartition1(Node head, int pivot) {
if (head == null || head.next == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
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];
}
public 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, index++, ++small);
} else if (nodeArr[index].value > pivot) {
swap(nodeArr, index, --big);
} else {
index++;
}
}
}
public static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
2）分成小、中、大三部分，再把各个部分之间串起来（面试用)
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;
Node node = head;
while (node != null) {
next = node.next;
node.next = null;
if (node.value < pivot) {
if (sH == null) {
sH = node;
sT = node;
} else {
sT.next = node;
sT = node;
}
} else if (node.value == pivot) {
if (eH == null) {
eH = node;
eT = node;
} else {
eT.next = node;
eT = node;
}
} else {
if (mH == null) {
mH = node;
mT = node;
} else {
mT.next = node;
mT = node;
}
}
node = next;
}
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);
}
4.单链表的复制
—种特殊的单链表节点类描述如下
class Node {
int value;
Node next;
Node rand;
Node(int val) {
value = val;
}
}
rand指针是单链表节点结构中新增的指针, rand可能指向链表中的任意一个节点，也可能指向null。
给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】
时间复杂度O(N)、额外空间复杂度O(1)
public static Node copyRandomList1(Node head) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
public static Node copyRandomList2(Node head){
if (head==null){
return head;
}
Node cur = head;
Node next = null;
while (cur!=null){
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
Node copy=null;
while (cur!=null){
next = cur.next.next;
copy = cur.next;
copy.random = cur.random==null?null:cur.random.next;
cur = next;
}
Node res = head.next;
cur = head;
while (cur!=null){
next = cur.next.next;
copy = cur.next;
cur.next = next;
copy.next = next!=null?next.next:null;
}
return res;
}
5.两个单链表的交点
给定两个可能有环也可能无环的单链表,头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
【要求】
如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
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 head;
}
Node fast = head.next;
Node slow = head.next.next;
while (fast.next != null && fast.next.next != null && fast != slow) {
fast = fast.next.next;
slow = slow.next;
}
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head1 == null) {
return null;
}
int size = 0;
Node cur1 = head1;
Node cur2 = head2;
while (cur1 != null) {
cur1 = cur1.next;
size++;
}
while (cur2 != null) {
cur2 = cur2.next;
size--;
}
if (cur1 != cur2) {
return null;
}
cur1 = head1;
cur2 = head2;
while (size < 0) {
cur2 = cur2.next;
}
while (size > 0) {
cur1 = cur1.next;
size--;
}
cur1 = head1;
cur2 = head2;
while (cur1 != null && cur2 != null && 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;
}
}
6.能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉?
不行，会有很多问题。
node = node.next;
node.next = node.next.next
这样无法删除最后一个节点，想要正确删除一个节点必须给单链表的head节点。
|