線性表面試題
排序面試題
鏈表是一種動態(tài)的數(shù)據(jù)結(jié)構(gòu)，因為在創(chuàng)建鏈表時，我們不需要知道鏈表的長度，當插入一個結(jié)點時，只需要為該結(jié)點分配內(nèi)存，然后調(diào)整指針的指向來確保新結(jié)點被連接到鏈表中。所以，它不像數(shù)組，內(nèi)存是一次性分配完畢的，而是每添加一個結(jié)點分配一次內(nèi)存。正是因為這點，所以它沒有閑置的內(nèi)存，比起數(shù)組，空間效率更高。
1)單向鏈表，雙向鏈表
單向：每個節(jié)點只有一個后繼指針next指向后面的節(jié)點，結(jié)尾通常指向null
雙向：包含兩個指針，prev指向前一節(jié)點，next指向后一節(jié)點
2)帶頭鏈表，不帶頭鏈表
3)循環(huán)的，非循環(huán)的
循環(huán)：特殊的單鏈表，尾結(jié)點指向頭節(jié)點
首先創(chuàng)建節(jié)點類：單鏈表中的節(jié)點應該具有兩個屬性：val 和 next。val存儲的該節(jié)點的數(shù)據(jù)值，next存儲下一個節(jié)點的地址。下面提供兩種創(chuàng)建鏈表的方式：分別是枚舉法和尾插法。
二叉樹面試題
圖算法面試題
高頻算法面試題
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
枚舉法：直接進行val的賦值以及對next的初始化。
public ListNode head;//鏈表的頭
public void creatList(){
ListNode listNode1 = new ListNode(11);
ListNode listNode2 = new ListNode(22);
ListNode listNode3 = new ListNode(33);
ListNode listNode4 = new ListNode(44);
this.head=listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
尾插法：插入第一個節(jié)點時，直接將該節(jié)點賦值給head,之后每次插入新節(jié)點都會通過head.next移動到最后一個節(jié)點cur，然后將新節(jié)點賦值給cur.next。
public ListNode head;//鏈表的頭
public void add(int data){
ListNode node = new ListNode(data);
if(this.head == null){
this.head = node;
}else {
ListNode cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
}
頭結(jié)點head是不動的，通過head.next不斷移動，在移動的過程中輸出鏈表的內(nèi)容。
public void display(){
ListNode cur = this.head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
思路：根據(jù)棧先進后出的特點，在遍歷鏈表時，把值按順序放入棧中，最后出棧就是逆序了。
/**
* 棧
*/
public List<Integer> printListFromQueue(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.add(listNode.value);
listNode = listNode.next;
}
List<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
思路：因為遞歸的本質(zhì)也是用的棧，所以先遞歸輸出它的后面節(jié)點，再輸出自己，這樣鏈表就反過來了。
/**
* 遞歸
*/
public List<Integer> printListFromDG(ListNode listNode) {
List<Integer> list = new ArrayList<>();
if (listNode != null) {
list.addAll(printListFromDG(listNode.next));
list.add(listNode.value);
}
return list;
}
將鏈表元素都賦值到數(shù)組中，然后可以從數(shù)組兩端向中間對比。
將鏈表元素全部壓棧，然后一邊出棧，一邊重新遍歷鏈表，一邊比較，只要有一個不相等，那就不是回文鏈表了。
public boolean isPalindrome(ListNode head) {
ListNode temp = head;
Stack<Integer> stack = new Stack();
//把鏈表節(jié)點的值存放到棧中
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
}
//然后再出棧
while (head != null) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
上面方法的改造，先遍歷第一遍，得到總長度。之后一遍歷鏈表，一遍壓棧。當?shù)竭_鏈表長度一半的位置之后，就不再壓棧，而是一邊出棧，一遍遍歷，一遍比較，只要有一個不相等，就不是回文鏈表。
public boolean isPalindrome(ListNode head) {
if (head == null)
return true;
ListNode temp = head;
Stack<Integer> stack = new Stack();
//鏈表的長度
int len = 0;
//把鏈表節(jié)點的值存放到棧中
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
len++;
}
//len長度除以2
len >>= 1;
//然后再出棧
while (len-- >= 0) {
if (head.val != stack.pop())
return false;
head = head.next;
}
return true;
}
我們使用快慢指針 ，fast一次走兩步，slow一次走一步。當fast到達表尾的時候，slow正好到達一半的位置，那么接下來可以從頭開始逆序一半的元素，或者從slow開始逆序一半的元素，都可以。
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;
//將前半部分鏈表反轉(zhuǎn)
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;
}
思路：循環(huán)鏈表將鏈表節(jié)點（注意是節(jié)點，不是節(jié)點里的值）存入到hashset中，如果元素添加不進去則證明有環(huán)。
public static boolean hasCycle1(ListNode head){
//存入的是ListNode類型而不是值
HashSet<ListNode> hashSet = new HashSet<>();
while (head!=null){
if (!hashSet.add(head)){
return true;
}
head=head.next;
}
return false;
}
復雜度分析：
時間復雜度：O(N)，其中 N 是鏈表中的節(jié)點數(shù)。最壞情況下我們需要遍歷每個節(jié)點一次。
空間復雜度：O(N)，其中 N 是鏈表中的節(jié)點數(shù)。主要為哈希表的開銷，最壞情況下我們需要將每個節(jié)點插入到哈希表中一次。
解決思路：定義兩個指針，一個指針每次移動一個位置為慢指針，一個指針每次移動兩個位置為快指針。當兩個指針相遇時就證明有環(huán)，如果快指針或者慢指針下一個節(jié)點為null，則證明無環(huán)。
為什么兩個指針一定會相遇呢？
兩個指針一旦進入環(huán)，遍歷的時候相當于無限循環(huán)因為出不出來環(huán)啊。想象一下時鐘，時針分針秒針在不同速度遍歷時是不是會相遇呢？
public static boolean hasCycle2(ListNode head){
if (head==null || head.next==null){
return false;
}
//定義兩個指針,快指針比慢指針多一步
ListNode slow = head;
ListNode fast = head.next;
while (slow!=fast){
if (fast==null||fast.next==null){
return false;
}
//快指針比慢指針多一步
slow=slow.next;
fast=fast.next.next;
}
return true;
}
復雜度分析
時間復雜度O(N) : 當鏈表中存在環(huán)時，每一輪移動后，快慢指針的距離將減小一。而初始距離為環(huán)的長度，因此至多移動 N 輪。
空間復雜度O(1) : 只使用了兩個指針額外的空間
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例：輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4
思路;雙指針思想
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現(xiàn)一次。
示例 1:輸入: 1->1->2 輸出: 1->2
示例 2:輸入: 1->1->2->3->3 輸出: 1->2->3
//一次遍歷，注意邊界條件。
public ListNode deleteDuplicates(ListNode head) { ? ?
ListNode cur = head; ? ?
while(cur != null && cur.next != null){ ? ? ? ?
if(cur.val == cur.next.val) ? ? ? ? ? ?
cur.next = cur.next.next; ? ? ? ?
else ? ? ? ? ? ?
cur = cur.next; ? ?
} ? ?
return head;
}?
給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。
示例：給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：給定的 n 保證是有效的。
//設置啞節(jié)點1，讓它走 n+1 步，再設置啞節(jié)點2，然后啞節(jié)點1和啞節(jié)點2一起移動，
//直到啞節(jié)點1走完鏈表，此時啞節(jié)點1和啞節(jié)點2之間正好隔著 n 個節(jié)點，再通過啞節(jié)點2刪除倒數(shù)第 n 個節(jié)點。
public ListNode removeNthFromEnd(ListNode head, int n) { ? ?
ListNode dummy = new ListNode(0); ? ?
dummy.next = head; ? ?
ListNode first = dummy; ? ?
for (int i = 1; i <= n + 1;i++){ ? ? ? ?
first = first.next; ? ?
} ? ?
ListNode second = dummy; ? ?
while(first != null){ ? ? ? ?
first = first.next; ? ? ? ?
second = second.next; ? ?
} ? ?
second.next = second.next.next; ? ?
return dummy.next;
}?
給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。
示例:給定 1->2->3->4, 你應該返回 2->1->4->3.
//設置啞節(jié)點，注意循環(huán)條件，指針移動的速度是2（因為需要兩兩交換節(jié)點）。
public ListNode swapPairs (ListNode head) { ? ?
ListNode dummy = new ListNode(-1); ? ?
dummy.next = head; ? ?
ListNode pre = dummy; ? ?
while (pre.next != null && pre.next.next != null) { ? ? ? ?
ListNode l1 = pre.next; ? ? ? ?
ListNode l2 = pre.next.next; ? ? ? ?
l1.next = l2.next; ? ? ? ?
l2.next = l1; ? ? ? ?
pre.next = l2; ? ? ? ?
pre = l1;
? ?} ? ?
return dummy.next;
}?
給定兩個非空鏈表來代表兩個非負整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個節(jié)點只存儲單個數(shù)字。將這兩數(shù)相加會返回一個新的鏈表。
你可以假設除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。
示例:輸入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出: 7 -> 8 -> 0 -> 7
//既然不能改變鏈表的結(jié)構(gòu)（翻轉(zhuǎn)鏈表），那就用一個棧來保存鏈表中的值，可以做到逆向輸出。
//相加部分的代碼邏輯就按常規(guī)思路寫。
public ListNode addTwoNumbers (ListNode l1, ListNode l2) { ? ?
Stack<Integer> l1Stack = listNodetoStack(l1); ? ?
Stack<Integer> l2Stack = listNodetoStack(l2); ? ?
int carry = 0; ? ?
ListNode head = new ListNode(-1); ? ?
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) { ? ? ? ?
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop(); ? ? ? ?
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop(); ? ? ? ?
int sum = x + y + carry; ? ? ? ?
ListNode node = new ListNode(sum % 10); ? ? ? ?
carry = sum / 10; ? ? ? ?
node.next = head.next; ? ? ? ?
head.next = node; ? ?
} ? ?
return head.next;
}
private Stack<Integer> listNodetoStack (ListNode head) { ? ?
Stack<Integer> stack = new Stack<>(); ? ?
while (head != null) { ? ? ? ?
stack.push(head.val); ? ? ? ?
head = head.next; ? ?
} ? ?
return stack;
}?
給定一個頭結(jié)點為 root 的鏈表, 編寫一個函數(shù)以將鏈表分隔為 k 個連續(xù)的部分。
每部分的長度應該盡可能的相等: 任意兩部分的長度差距不能超過 1，也就是說可能有些部分為 null。
這k個部分應該按照在鏈表中出現(xiàn)的順序進行輸出，并且排在前面的部分的長度應該大于或等于后面的長度。
返回一個符合上述規(guī)則的鏈表的列表。
舉例： 1->2->3->4, k = 5 // 5 結(jié)果 [ [1], [2], [3], [4], null ]
示例 1：
輸入: root = [1, 2, 3], k = 5 輸出: [[1],[2],[3],[],[]] 解釋: 輸入輸出各部分都應該是鏈表，而不是數(shù)組。 例如, 輸入的結(jié)點 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。 第一個輸出 output[0] 是 output[0].val = 1, output[0].next = null。 最后一個元素 output[4] 為 null, 它代表了最后一個部分為空鏈表。
示例 2：
輸入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] 解釋: 輸入被分成了幾個連續(xù)的部分，并且每部分的長度相差不超過1.前面部分的長度大于等于后面部分的長度。
提示:
● root 的長度范圍： [0, 1000].
● 輸入的每個節(jié)點的大小范圍：[0, 999].
● k 的取值范圍： [1, 50].
/*思路：先統(tǒng)計出鏈表長度，除以 k, 求商和余數(shù)，其中：
● 余數(shù)代表最后結(jié)果中有多少個長鏈表
● 商代表每個短鏈表的長度（結(jié)果集中后部的鏈表）
● 長鏈表比短鏈表多一個節(jié)點*/
public ListNode[] splitListToParts (ListNode root, int k) { ? ?
ListNode cur = root; ? ?
int len = 0; ? ?
while (cur != null) { ? ? ? ?
cur = cur.next; ? ? ? ?
len++; ? ?
} ? ?
int mod = len % k; ? ?
int size = len / k; ? ?
cur = root; ? ?
ListNode[] ans = new ListNode[k]; ? ?
for (int i = 0; cur != null && i < k; i++) { ? ? ? ?
ans[i] = cur; ? ? ? ?
int curSize = size + (mod-- > 0 ? 1 : 0); ? ? ? ?
for (int j = 0; j < curSize - 1; j++) { ? ? ? ? ? ?
cur = cur.next; ? ? ? ?
} ? ? ? ?
ListNode next = cur.next; ? ? ? ?
cur.next = null; ? ? ? ?
cur = next; ? ?
} ? ?
return ans;
}?
給定一個單鏈表，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起。請注意，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性，而不是節(jié)點的值的奇偶性。
請嘗試使用原地算法完成。你的算法的空間復雜度應為 O(1)，時間復雜度應為 O(nodes)，nodes 為節(jié)點總數(shù)。
示例 1:輸入: 1->2->3->4->5->NULL 輸出: 1->3->5->2->4->NULL
示例 2:輸入: 2->1->3->5->6->4->7->NULL 輸出: 2->3->6->7->1->5->4->NULL
說明:
● 應當保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序。
● 鏈表的第一個節(jié)點視為奇數(shù)節(jié)點，第二個節(jié)點視為偶數(shù)節(jié)點，以此類推。
設置三個指針，其中奇指針和偶指針是很自然能想到的，evenHead起輔助作用，用于將奇鏈表和偶鏈表結(jié)合起來。
public ListNode oddEvenList (ListNode head) { ? ?
ListNode odd = head; ? ?
ListNode even = head.next; ? ?
ListNode evenHead = even; ? ?
while (even != null && even.next != null) { ? ? ? ?
odd.next = even.next; ? ? ? ?
odd = odd.next;
? ? ? ? even.next = odd.next;
? ? ? ? even = even.next;
? ? }
? ? odd.next = evenHead;
? ? return head;
}
官方微信
官方抖音
京公網(wǎng)安備 11030102010736號