【Java算法题】剑指offer_01数据结构

前言

刷题链接：
https://www.nowcoder.com/exam/oj/ta?page=2&tpId=13&type=265

1. 链表

JZ24 反转链表

思路：基本操作，如下所示。

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {if(head == null){return null;}ListNode pre = null;ListNode cur = head;ListNode temp = null;while(cur != null){temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

JZ6 从尾到头打印链表

思路：

1. 反转链表
2. 添加元素至数组

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ArrayList<Integer> arr = new ArrayList<Integer>();// 1. 链表不为空，则反转链表if(listNode!=null){listNode = ReverseList(listNode);// 2. 添加元素到ArrayListListNode cur = listNode;while(cur!=null){arr.add(cur.val);cur = cur.next;}return arr;}return arr; // 空链表返回空ArrayList}public ListNode ReverseList(ListNode head){ //反转链表ListNode pre = null;ListNode cur = head;ListNode temp = cur.next;while(cur != null){temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

JZ25 合并两个排序的链表

思路：看代码很清楚，利用新的lsit存排序后的链表，小的先存。

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {ListNode list = new ListNode(0);ListNode l = list;if(list1 == null || list2 == null){return list1 != null?list1:list2;}while(list1!=null && list2!=null){if(list1.val<=list2.val){l.next = list1;list1=list1.next;}else{l.next = list2;list2=list2.next;}l=l.next;}if(list1!=null){l.next = list1; }if(list2!=null){l.next = list2;}return list.next;}
}

JZ52 两个链表的第一个公共节点

思路：Y字形链表，以相同的速度遍历两条链表最终总会相遇。（注意：当遍历链表1结束，将指针指向链表2的头。）

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode p1=pHead1, p2=pHead2;while(p1!=p2){p1 = (p1==null)?pHead2:p1.next;p2 = (p2==null)?pHead1:p2.next;}return p1;}
}

JZ23 链表中环的入口结点

思路：
快慢指针，快指针走两步，慢指针走一步。

1. 判断是否有环；
2. 有环则将slow指针指向头，fast从相遇点出发，二者将在入环点相遇。

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) {ListNode fast = pHead;ListNode slow = pHead;while(fast.next!=null && fast.next.next!=null){fast = fast.next.next;slow = slow.next;if(fast==slow){ //判断有没有环break;}}if(fast.next==null || fast.next.next==null){ //无环返回nullreturn null;}slow = pHead;while (slow != fast) { //找到环入口fast = fast.next;slow = slow.next;}return fast;}
}

JZ22 链表中倒数最后k个结点

思路：快慢指针，先让一个指针走k步，后面同步一个个走，快指针走到末尾的时慢指针刚好指向末尾第k个节点。

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead ListNode类 * @param k int整型 * @return ListNode类*/public ListNode FindKthToTail (ListNode pHead, int k) {// write code hereif(pHead == null){return null;}ListNode slow = pHead;ListNode fast = pHead;while(k-->0){if(fast == null)return null;fast = fast.next; //先走k步}while(fast != null){fast = fast.next;slow = slow.next;}return slow;}
}

JZ35 复杂链表的复制

思路：参考这篇博客 https://blog.csdn.net/qq_43676757/article/details/106253305

使用常规方法一，将步骤分成三个：

1. 复制节点
   

2. 复制random节点给已拷贝节点
   

3. 拆分链表
   

/*
public class RandomListNode {int label;RandomListNode next = null;RandomListNode random = null;RandomListNode(int label) {this.label = label;}
}
*/
public class Solution {public RandomListNode Clone(RandomListNode pHead) {if(pHead==null)return null;RandomListNode cur = pHead;//遍历原始链表，复制while(cur!=null){//拷贝节点RandomListNode temp = new RandomListNode(cur.label);//添加新节点到原始链表当前节点后面temp.next=cur.next;cur.next=temp;cur=temp.next;}//连接新链表的random节点cur = pHead;//回到头节点RandomListNode temp = pHead.next;while(cur!=null){if(cur.random==null){temp.random=null;}else{temp.random = cur.random.next; //新链表的random为cur的random下一个}cur = cur.next.next;if(temp.next!=null){temp=temp.next.next;}}//拆分链表cur = pHead;RandomListNode res = pHead.next;temp = res;while(cur!=null){cur.next=cur.next.next;cur=cur.next;if(temp.next!=null){temp.next = temp.next.next;}temp = temp.next;}return res;}
}

JZ76 删除链表中重复的结点

思路：需要前一个节点、当前节点和下一节点的信息。在表头添加一个节点作为pre，当前节点和下一节点相同的时候，当前指针往下移动；当数值不同的时才退出循环，将pre.next指向下一个节点。

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode deleteDuplication(ListNode pHead) {// 链表为空或者只有一个节点if(pHead == null || pHead.next==null){return pHead;}ListNode res = new ListNode(-1); //表头加一个节点res.next = pHead;ListNode pre = res;ListNode cur = pHead;while(cur!=null && cur.next!=null){if(cur.val == cur.next.val){ //相邻的节点值相同int tmp = cur.val;while(cur.next!=null && cur.next.val==tmp){cur = cur.next; //跳过相同的节点    }//退出循环时，cur指向最后一个重复值cur = cur.next;pre.next = cur;}else{pre=cur;cur=cur.next;}}return res.next;}
}

JZ18 删除链表的节点

思路：直观的想法就是记录下前一个节点，当搜索到匹配的数值，将前一个节点的next直接指向当前节点的下一个节点，达到删除当前节点的目的。特殊情况是表头节点满足条件！

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param val int整型 * @return ListNode类*/public ListNode deleteNode (ListNode head, int val) {// write code here//1. 空则返回nullif(head == null){ return null;}ListNode pre = head; //pre记录当前节点前一个节点ListNode cur = head.next;//2.第一个元素就满足val，删除第一个元素if(pre!=null&&pre.val==val){pre=pre.next;return pre;}//3.第二个元素开始匹配while(cur!=null){if(cur.val==val){pre.next = cur.next;cur.next = null;break;}cur = cur.next;pre = pre.next;}return head;}
}

更简洁的代码（来源牛客网题解）：在单链表前再加一个节点( ListNode res = new ListNode(0); res.next = head; )，返回的时候记得去掉。

import java.util.*;
public class Solution {public ListNode deleteNode (ListNode head, int val) {//加入一个头节点ListNode res = new ListNode(0);res.next = head;//前序节点ListNode pre = res;//当前节点ListNode cur = head;//遍历链表while(cur != null){//找到目标节点if(cur.val == val){//断开连接pre.next = cur.next;break;}pre = cur;cur = cur.next;}//返回去掉头节点return res.next;}
}

---

2. 树