1. 新浪面試：請設計一個單鏈表，給定頭結點和整數k，回傳單鏈表倒數第k個結點，
代碼[Java實作]：
/**
* 回傳單鏈表倒數第k個結點: [新浪面試題 & 劍指Offer.22]
* 思路：1. 接收頭結點和k值
* 2. 整體遍歷，得到鏈表長度
* 3. 再次遍歷，回傳（len-k）個值即為倒數第k個結點
* @author KyleHsu
*/
public Node lastKNode(Node head,int k){
// 沒有結點，沒有找到
if (head.next == null){
return null;
}
int len = SinglelinkedlistTest.getLen(head);
// 如果給的k不在鏈表長度范圍內，肯定找不到
if (k<=0 || k>len){
return null;
}
Node temp = head.next;
for (int i = 0; i < (len-k); i++) {
temp = temp.next;
}
return temp;
}
/**
* 回傳單鏈表的有效節點個數
* @author KyleHsu
*/
public static int getLen(Node head){
if (head.next == null){
return 0;
}
int length = 0;
Node temp = head.next;
while (temp != null){
temp = temp.next;
length++;
}
return length;
}
2. 騰訊面試：請設計一個單鏈表，給定頭結點，將其反轉，
/**
* 反轉一個單鏈表: [騰訊面試題 & 劍指Offer.24]：
* 思路1：頭插法：實際上只是用了一個輔助temp指標和一個新的頭結點把原來的單鏈表進行了反轉，并沒有制造新的鏈表
* 思路2：使用堆疊的特性 - 后進先出
* 思路3：遞回反轉
*/
public static void reverseLinkedlist(Node head){
// 考慮意外情況
if (head.next == null){
throw new RuntimeException("當前鏈表為空，無需進行反轉~~");
}
if (head.next.next == null){
throw new RuntimeException("當前鏈表僅有一個結點，無需進項反轉~~");
}
/**
* 使用頭插法進行反轉:
* 1.創建一個新的頭結點,用于臨時連接新的結點
* 2.創建一個輔助結點，用于指向原鏈表的第一個結點，逐個去除原鏈表的結點，然后連接到新鏈表頭結點的第一個
*
* next = cur.next;//先暫時保存當前節點的下一個節點，因為后面需要使用
* cur.next = reverseHead.next;//將cur的下一個節點指向新的鏈表的最前端
* reverseHead.next = cur; //將cur 連接到新的鏈表上
* cur = next;//讓cur后移
*/
Node newHead = new Node(0,"","");
Node temp = head.next;
Node tempNext = null;
// 只要原鏈表中還有結點就一直往后找
while (temp != null){
tempNext = temp.next; // 先保存第一個結點的后一根線
temp.next = newHead.next; //拋棄第一個結點的前一根線
newHead.next = temp; //再接上第一個結點的前一根線
temp = tempNext; // 接上第一個結點的后一根線
}
// 接上頭結點
head.next = newHead.next;
}
3. 百度面試：請設計一個單鏈表，給定頭結點，將其逆序列印，
/**
* 逆序列印單鏈表：[百度面試題]：
* 方式一：利用剛才反轉的單鏈表，然后直接遍歷即可，但是由于反轉了原來的單鏈表會破壞掉鏈表的結構，所以不推薦！
* 方式二：利用堆疊的特點 - 后進先出
*
* 其實本題思路和騰訊面試題相同，只是換了堆疊的方式實作而已
*
*/
public static void reversePrint(Node head){
// 考慮意外情況
if (head.next == null){
throw new RuntimeException("當前鏈表為空，無需進行反轉~~");
}
Stack<Node> nodes = new Stack<>();
Node temp = head.next;
while (temp != null){
// 壓堆疊
nodes.push(temp);
temp = temp.next;
}
while (nodes.size() > 0){
System.out.println(nodes.pop());
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296191.html
標籤：其他