1、链表
1、两数之和
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 使用非常常规的解法ListNode pre = new ListNode(0);ListNode cur = pre;int carry = 0;while (l1 != null || l2 != null){int num1 = l1 == null ? 0 : l1.val;int num2 = l2 == null ? 0 : l2.val;// 获取总和int sum = num1 + num2 + carry;// 取余cur.next = new ListNode(sum % 10);carry = sum / 10;// 下一次循环cur = cur.next;if (l1 != null){l1 = l1.next;}if (l2 != null){l2 = l2.next;}}if (carry == 1){cur.next = new ListNode(carry);}return pre.next;
2、删除链表倒数节点
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; ++i) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;
}
3、合并两个有序列表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
4、合并n个有序链表
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
5、两两交换链表的节点
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
6、K个一组翻转链表
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
if(k == 0) return head;
ListNode tail = head, newtail = head;
ListNode newhead;
int n = 1;
// 原来的尾结点指向原来的头结点，形成环
while(tail.next != null){
tail = tail.next;
n++;
}
tail.next = head;
// 找到断开环的位置
for(int i = 0; i < (n - k % n - 1); i++){
newtail = newtail.next;
}
// 新的头结点指向断开环的位置
newhead = newtail.next;
newtail.next = null;
return newhead;
}
7、旋转链表
public ListNode rotateRight(ListNode head, int k) {
ListNode temp = head;
ListNode left = head;
ListNode right = head;
if (head == null) return null;
// 计算链表长度
ListNode count = head;
int n = 1;
while (count.next != null){
count = count.next;
n++;
}
k = k % n;
if (k <=0 || head.next == null) return head;
// 双指针 找到k的位置
for (int i = 0; i<k && right.next != null;i++){
right = right.next;
}
// 将链表成环
while (right.next != null){
left = left.next;
// 为k的位置
right = right.next;
}
ListNode resNode = left.next;
right.next = temp;
left.next = null;
return resNode;
}
8、删除重复的节点（不留）
public ListNode deleteDuplicates(ListNode head) {
// 没有节点或者只有一个节点，必然没有重复元素
if (head == null || head.next == null) return head;
// 当前节点和下一个节点，值不同，则head的值是需要保留的，对head.next继续递归
if (head.val != head.next.val) {
head.next = deleteDuplicates(head.next);
return head;
} else {
// 当前节点与下一个节点的值重复了，重复的值都不能要。
// 一直往下找，找到不重复的节点。返回对不重复节点的递归结果
ListNode notDup = head.next.next;
while (notDup != null && notDup.val == head.val) {
notDup = notDup.next;
}
return deleteDuplicates(notDup);
}
}
9、删除重复的节点（留）
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode right = head;
while (right.next != null){
if (right.val == right.next.val){
right.next = right.next.next;
}else{
right = right.next;
}
}
return head;
}
10、翻转链表
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode slow = dummy;
ListNode fast = dummy;
if (head == null)return head;
// 快指针先走一段时间
for (int i = 0;i< right-left + 1 && fast != null;i++) fast = fast.next;
// 慢指针走到 入前指针前一个节点
for (int j = 0;j< left -1 && fast != null;j++){
pre = pre.next;
fast = fast.next;
}
ListNode last = fast.next;
fast.next = null;
ListNode leftNode = pre.next;
pre.next = null;
reverse(leftNode);
// 拼接前面
pre.next = fast;
leftNode.next = last;
return dummy.next;
}
public ListNode reverse(ListNode head){
ListNode pre = null;
ListNode right = head;
while (right != null){
ListNode next = right.next;
right.next = pre;
pre = right;
right = next;
}
return pre;
}
11、二叉树展开为链表
public void flatten(TreeNode root) {
while (root != null){
// 判断是否存在左子树
if (root.left == null){
root = root.right;
}else{
TreeNode pre = root.left;
// 找到左子节点的最右节点
while (pre.right != null){
pre = pre.right;
}
// 将pre 的右节点接root的右节点
pre.right = root.right;
// root 的右节点接root 的左节点
root.right = root.left;
// 下面两步为将root 到下一个节点循环
root.left = null;
root = root.right;
}
}
}
12、复制设计链表
public Node copyRandomList(Node head) {
if(head==null) {
return null;
}
Node p = head;
//第一步，在每个原节点后面创建一个新节点
//1->1'->2->2'->3->3'
while(p!=null) {
Node newNode = new Node(p.val);
newNode.next = p.next;
p.next = newNode;
p = newNode.next;
}
p = head;
//第二步，设置新节点的随机节点
while(p!=null) {
if(p.random!=null) {
p.next.random = p.random.next;
}
p = p.next.next;
}
Node dummy = new Node(-1);
p = head;
Node cur = dummy;
//第三步，将两个链表分离
while(p!=null) {
cur.next = p.next;
cur = cur.next;
p.next = cur.next;
p = p.next;
}
return dummy.next;
}
13、排序链表
public ListNode insertionSortList(ListNode head) {
if (head == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 定义前后节点来查找
ListNode lastNode = head;
ListNode curr = head.next;
while (curr != null){
if (lastNode.val <= curr.val){
lastNode = lastNode.next;
}else{
ListNode pre = dummy;
// 找到最佳位置
while (pre.next.val <= curr.val){
pre = pre.next;
}
// 后面删除当前节点
lastNode.next = curr.next;
// 在找到的位置处插入
curr.next = pre.next;
pre.next = curr;
}
curr = lastNode.next;
}
return dummy.next;
}
14、相交链表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
// 两个链表 循环2次就是相交点
ListNode curA = headA;
ListNode curB = headB;
while (curA != curB){
curA = curA == null ? headB : curA.next;
curB = curB == null ? headA : curB.next;
}
return curA;
}
public ListNode getIntersectionNode(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null)return null;
ListNode curr1 = head1;
ListNode curr2 = head2;
int n = 0;
while (curr1.next != null){
n++;
curr1 = curr1.next;
}
while (curr2.next != null){
n--;
curr2 = curr2.next;
}
if (curr1 != curr2)return null;
curr1 = n > 0 ? head1 : head2;
curr2 = curr1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0){
n--;
curr1 = curr1.next;
}
while (curr1 != curr2){
curr1 = curr1.next;
curr2 = curr2.next;
}
return curr1;
}
15、翻转链表元素
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 返回最后一个
ListNode curr = reverseList(head.next);
// 将指针逆转 下一个的next指向当前这一个
head.next.next = head;
head.next = null;
return curr;
}
16、回文链表
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
// 也是使用栈 n/2 时间复杂度
public static boolean isPalindrome2(Node head){
if (head == null || head.next == null)return true;
Node right = head.next;
Stack<Node> stack = new Stack<>();
Node cur = head;
// 快慢指针
while (cur.next != null && cur.next.next != null){
right = right.next;
cur = cur.next.next;
}
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、树
1、是否为平衡二叉树
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
public static class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public static boolean isBalanced(Node head){
return process(head).isBalanced;
}
// 递归过程
private static ReturnType process(Node head) {
if (head == null){
return new ReturnType(true, 0);
}
// 判断左边是否为平衡二叉树
ReturnType leftData = process(head.left);
ReturnType rightData = process(head.right);
// 下面是条件判断
int height = Math.max(leftData.height,rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced
&& Math.abs(leftData.height - rightData.height) <2;
return new ReturnType(isBalanced,height);
}
2、是否为搜索二叉树
// 中序遍历 判断是否为搜索二叉树
public static boolean checkBST2(Node head){
System.out.println("in-order");
if (head != null){
Stack<Node> stack = new Stack<>();
int preValue = Integer.MIN_VALUE;
while (!stack.isEmpty() || head != null){
if (head != null){
stack.push(head);
head = head.left;
}else {
head = stack.pop();
if (head.value <= preValue){
return false;
}else {
preValue = head.value;
}
head = head.right;
}
}
}
return true;
}
3、遍历二叉树
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
public static void proOrderUnRecur(Node head) {
System.out.println("pre-order");
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
// 先入右再入左
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
System.out.println();
}
// 中序遍历
public static void inOrderRecur(Node head){
System.out.println("in-order");
if (head != null){
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || head != null){
if (head != null){
stack.push(head);
head = head.left;
}else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
// 后序遍历
public static void posOrderUnRecur(Node head) {
System.out.println("pos-order");
if (head != null) {
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()){
System.out.print(s2.pop()+" ");
}
}
System.out.println();
}
4、序列化
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
// 以head为头来序列化
public static String serialByPre(Node head){
if (head == null){
return "#_";
}
String res = head.value + "_";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
public static Node reconByPreString(String preStr){
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < values.length; i++) {
queue.add(values[i]);
}
return reconPreOrder(queue);
}
private static Node reconPreOrder(Queue<String> queue) {
String value = queue.poll();
if (value.equals("#")){
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
5、分区
public static class Node{
public int value;
public Node next;
public Node(int data){
this.value = data;
}
}
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;
}
}
head = 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);
}
6、最大层数
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
// 宽度优先遍历 层次优先遍历 Node
public static int wNode(Node head){
if (head == null){
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node, Integer> levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1;
int curLevelNodes = 0;
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()){
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if (curNodeLevel == curLevel){
curLevelNodes++;
}else {
max = Math.max(max,curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
if (cur.left != null){
levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
}
if (cur.right != null){
levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
}
}
return max;
}
7、是否为对称二叉树
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetricFun(root.left, root.right);
}
public boolean isSymmetricFun(TreeNode left, TreeNode right){
// 下面两行的判断是否有一个为null 一个不为空
if (left == null && right == null) return true;
if (left == null || right == null) return false;
// 比较
if (left.val != right.val) return false;
return isSymmetricFun(left.left, right.right) && isSymmetricFun(left.right, right.left);
}
8、翻转二叉树
public TreeNode invertTree(TreeNode root) {
if(root==null) {
return null;
}
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//返回处理完的根节点
return root;
}
若有收获，就点个赞吧
0 人点赞
