单向链表反转
// 通过递归的方式找到最后的节点
// 指向前面的节点，这样可以不破坏之前的指向回溯回去
public static Node reverseLinkedNode(Node head) {if (head == null || head.next == null) {// 返回最后的节点return head;}Node nextNode = reverseLinkedNode(head.next);nextNode.next = head;head.next = null;return head;
}
// 直接反转
public static Node reverse(Node head) {Node next = null;Node pre = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;
}
题目中nextNode永远会返回head的下一个节点
双向链表反转
用两个node记录下来当前节点的前后环境
public static DDNode reverse(DDNode head) {DDNode pre = null;DDNode next = null;while(head != null) {next = head.next;head.next = pre;head.pre = next;pre = head;head = next;}return pre;
}
打印两个有序列表的公共部分
主要思想和归并排序有些像，因为是有序的链表
所以同时从头开始对比大小，小的一方就next，直到相等后同时记录后，next
有任何一方遍历到结束就返回结果
public static List<Integer> getOverlap(Node n1, Node n22) {if (n1 == null || n22 == null) {return null;}List<Integer> result = new ArrayList<>();int v1, v2;while(n1 != null && n22 != null) {v1 = n1.value;v2 = n22.value;if (v1 == v2) {result.add(v1);n1 = n1.next;n22 = n22.next;} else if (v1 > v2) {n22 = n22.next;} else {n1 = n1.next;}}return result;
}
判断是不是回文链表
回文链表：1->2->3->2->1
思路：用栈记录后出站和原来列表对比，因为栈是逆序，如果逆序和链表仍然相等
则是回文链表
public static boolean isMirror(Node head) {Stack<Node> stack = new Stack<>();Node node = head;while (head != null) {stack.push(head);head = head.next;}boolean result = true;while (node != null) {if (node.value != stack.pop().value) {System.out.println(node.value);result = false;return result;}node = node.next;}return result;
}
链表排序
把链表转换为数组，然后进行快速排序，再转换为链表
public static Node nodeSort(Node head) {List<Node> nodes = new ArrayList<>();while (head != null) {nodes.add(head);head = head.next;}if (nodes.size() <= 1) {return head;}return qs(nodes, 0, nodes.size() - 1);
}
// 返回头节点
public static Node qs(List<Node> nodes, int low, int high) {if (high <= low) {return null;}int partition = partition(nodes, low, high);qs(nodes, low, partition - 1);qs(nodes, partition + 1, high);for(int i = 0; i< nodes.size();i++) {if (i + 1 < nodes.size()) {nodes.get(i).next = nodes.get(i + 1);} else {nodes.get(i).next = null;}}return nodes.get(0);
}
public static int partition(List<Node> nodes, int low, int high) {Node standard = nodes.get(low);while (low < high) {while (low < high && nodes.get(high).value >= standard.value) {high --;}swap(nodes, low, high);while (low < high && nodes.get(low).value <= standard.value) {low ++;}swap(nodes, high, low);}nodes.set(low, standard);return low;
}
判断链表是否有环，并返回入环节点
一. 使用HashSet存储如果存在重复存储元素则有环
public static Node getCycleNode(Node head) {HashSet<Node> hashSet = new HashSet<>();while (head != null) {if (!hashSet.contains(head)) {hashSet.add(head);} else {return head;}head = head.next;}return null;
}
二. 使用快慢指针
快指针一次走两个，慢指针一次一步，
当快慢指针相遇时说明有环，此时让快指针回到原点，再相遇时就是入环节点
public static Node getCycleNode2(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node quick = head.next;Node slow = head.next.next;while (quick != slow) {quick = quick.next;slow = slow.next.next;}quick = head;while (quick != slow) {quick = quick.next;slow = slow.next;}return quick;
}