假設(shè)你正在應(yīng)聘華為外包公司的Java開發(fā)崗位,以下是一個可能的面試題案例:
面試題目:Java實(shí)現(xiàn)單鏈表的逆序
問題描述:
請編寫一個Java程序,實(shí)現(xiàn)對單鏈表的逆序操作。給定一個單鏈表的頭節(jié)點(diǎn),要求將鏈表的所有節(jié)點(diǎn)反轉(zhuǎn),并返回反轉(zhuǎn)后的頭節(jié)點(diǎn)。
示例:
假設(shè)鏈表為:1 -> 2 -> 3 -> 4 -> 5
反轉(zhuǎn)后應(yīng)該為:5 -> 4 -> 3 -> 2 -> 1
解題思路:
實(shí)現(xiàn)單鏈表的逆序操作可以使用迭代或遞歸的方法。下面將為大家提供使用迭代的解題思路。
解題步驟:
1. 定義三個指針:prev(記錄前一個節(jié)點(diǎn))、current(記錄當(dāng)前節(jié)點(diǎn))、next(記錄當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn))。
2. 初始時,prev指向null,current指向頭節(jié)點(diǎn)。
3. 在循環(huán)中,將current的next指針指向prev,然后將prev指向current,current指向next。
4. 重復(fù)上述步驟,直到current指向null(到達(dá)鏈表的末尾)。
Java代碼實(shí)現(xiàn):
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public class ReverseLinkedList {
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode current = head;
ListNode next = null;
while (current != null) {
next = current.next; // 先保存當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
current.next = prev; // 當(dāng)前節(jié)點(diǎn)的next指針指向前一個節(jié)點(diǎn)
prev = current; // prev指向當(dāng)前節(jié)點(diǎn),相當(dāng)于前移一步
current = next; // current指向下一個節(jié)點(diǎn),相當(dāng)于前移一步
}
return prev; // prev指向原鏈表的最后一個節(jié)點(diǎn),即反轉(zhuǎn)后的頭節(jié)點(diǎn)
}
// 測試
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ReverseLinkedList solution = new ReverseLinkedList();
ListNode reversedHead = solution.reverse(head);
// 打印反轉(zhuǎn)后的鏈表
while (reversedHead != null) {
System.out.print(reversedHead.val + " -> ");
reversedHead = reversedHead.next;
}
System.out.print("null");
}
}
這是一個典型的面試題目,面試官可能會根據(jù)你的解答展開更多問題,例如如何使用遞歸實(shí)現(xiàn)鏈表逆序,或者如何處理特殊情況(如空鏈表)。在面試過程中,除了正確的解答問題,展示良好的溝通和思考能力也是非常重要的。希望以上面試題案例對你有所幫助!