Java 八道經(jīng)典面試題之鏈表題
第一題 移除鏈表元素
給你一個鏈表的頭節(jié)點(diǎn) head 和一個整數(shù) val ，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點(diǎn)，并返回 新的頭節(jié)點(diǎn) 。
輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]
這道題還是比較簡單的我們需要讓刪除的節(jié)點(diǎn)的前一個結(jié)點(diǎn)指向刪除節(jié)點(diǎn)的后一個就行。就比如cur.next==cur.next.next;。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode header=new ListNode(-1);
header.next=head;
ListNode cur =header;
while(cur.next!=null){
if(cur.next.val==val){
cur.next=cur.next.next;
}else{
cur=cur.next;
}
}
return header.next;
}
}
第二題 反轉(zhuǎn)鏈表
給你單鏈表的頭節(jié)點(diǎn) head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
這也是一個簡單題，我們還是先弄一個尾結(jié)點(diǎn)，因為鏈表的最后一個結(jié)點(diǎn)的下一個是一個null，這道題我們可以通過一次循環(huán)讓后一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)指向前一個結(jié)點(diǎn)。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre =null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
第三題 鏈表的中心結(jié)點(diǎn)
給定一個頭結(jié)點(diǎn)為 head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。
如果有兩個中間結(jié)點(diǎn)，則返回第二個中間結(jié)點(diǎn)。
答：這個也是一個簡單題我們需要用到快慢指針，當(dāng)快指針指完之后，慢的結(jié)點(diǎn)肯定是中點(diǎn)比如18 快的可以走9步每次走兩步走到18，慢的可以每次走一部走9步。剛好到中點(diǎn)。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p =head;
ListNode q =head;
while(q!=null&&q.next!=null){
q=q.next.next;
p=p.next;
}
return p;
}
}
第四題 倒數(shù)第k個結(jié)點(diǎn)
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點(diǎn)
輸入：
1,{1,2,3,4,5}
復(fù)制
返回值：
{5}
答：這道題也是一個簡單題，直接簡單粗暴的搞出來倒數(shù)第k個點(diǎn)的值就行；
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode cur=head;
ListNode pre=head;
int count=0;
int x=0;
while(cur!=null){
cur=cur.next;
count++;
}
if(k<0||k>count){
return null;
}
while(pre!=null){
if(x==count-k){
break;
}else{
pre=pre.next;
x++;
}
}
return pre;
}
}
這道題寫的有點(diǎn)麻煩了，我們也可以用快慢指針做。一個指針走5步一個走4步。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode p=head;
ListNode q=head;
for(int i = 0; i < k; i++) {
if (p != null) {
p= p.next;
} else {
return null;
}
}
while(p!=null){
p=p.next;
q=q.next;
}
return q;
}
}
第五題 合并兩個有序鏈表
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
答：這道題考到了怎么將兩個鏈表合并，我們需要將兩個鏈表從大到小合并起來。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// 任一為空，直接連接另一條鏈表
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummyHead.next;
}
}
第六題 鏈表分割
現(xiàn)有一鏈表的頭指針 ListNode* pHead，給一定值x，編寫一段代碼將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前，且不能改變原來的數(shù)據(jù)順序，返回重新排列后的鏈表的頭指針。
輸入：l1 = [1,2，1,3,2] 3
輸出：[1，2，1，2，3]
這道題比較難了需要我們創(chuàng)建兩個鏈表，一個數(shù)大與等于x的鏈表，另一個數(shù)小于x的鏈表。然后讓上一個鏈表的下一個尾結(jié)點(diǎn)指向下一個結(jié)點(diǎn)的尾巴結(jié)點(diǎn)。
這里我們需要用到如何將兩個鏈表合并成一個鏈表。
做題的時候先想怎么做然后在動手！
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if(pHead == null || pHead.next == null) {
return pHead;
}
ListNode newHead = new ListNode(0);
ListNode flagHead = new ListNode(0);
ListNode newh = newHead;
ListNode flagh = flagHead;
while(pHead != null){
if(pHead.val < x){
newh.next = new ListNode(pHead.val);
newh = newh.next;
}else{
flagh.next = new ListNode(pHead.val);
flagh = flagh.next;
}
pHead = pHead.next;
}
newh.next = flagHead.next;
return newHead.next;
}
}
第七題 判斷是否回文
對于一個鏈表，請設(shè)計一個時間復(fù)雜度為O(n),額外空間復(fù)雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。
給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結(jié)構(gòu)。保證鏈表長度小于等于900。
1->2->2->1
返回：true
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
// write code here
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode cur=slow.next；
while(cur!=null){
ListNode curNext=cur.next;
cur.next=slow;
slow=cur;
cur=curNext;
}
//3.一個從前往后，一個從后往前 如果相遇，則證明回文
while(head!=slow){
if(head.val!=slow.val){//先判斷值是否相等
return false;
}
if(head.next==slow){//偶數(shù)情況下
return true;
}
head=head.next;
slow=slow.next;
}
return true;
}
第八題 相交鏈表
給你兩個單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點(diǎn)。如果兩個鏈表不存在相交節(jié)點(diǎn)，返回 null 。
可以用笨方法就是計算出來每個鏈表的個數(shù)然后讓多的先走。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode last = headB;
while (last.next != null) {
last = last.next;
}
last.next = headB;
ListNode fast = headA;
ListNode slow = headA;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = headA;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
last.next = null;
return fast;
}
}
last.next = null;
return null;
}
}
到此這篇關(guān)于Java 八道經(jīng)典面試題之鏈表題的文章就介紹到這了,更多相關(guān)Java 鏈表題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
筆者前幾日在開服過程中需要將字符串轉(zhuǎn)化成為16進(jìn)制的字符串,在網(wǎng)上找到了一些方法嘗試之后,均發(fā)現(xiàn)存在一個問題-->字符串轉(zhuǎn)為16進(jìn)制后再轉(zhuǎn)回來,英文正常,中文出現(xiàn)亂碼2009-05-05
這篇文章主要介紹了Java多線程處理List數(shù)據(jù)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
詳解基于Spring Boot與Spring Data JPA的多數(shù)據(jù)源配置
本篇文章主要介紹了詳解基于Spring Boot與Spring Data JPA的多數(shù)據(jù)源配置，非常具有實(shí)用價值，需要的朋友可以參考下2017-05-05
深入剖析springBoot中的@Scheduled執(zhí)行原理
這篇文章主要介紹了springBoot中的@Scheduled執(zhí)行原理，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
SpringBoot中HttpSessionListener的簡單使用方式
這篇文章主要介紹了SpringBoot中HttpSessionListener的簡單使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
本文給大家介紹了SpringBoot的Run方法，文中通過實(shí)例代碼相結(jié)合給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-10-10
SpringBoot2.x版本中,使用SpringSession踩的坑及解決
這篇文章主要介紹了SpringBoot2.x版本中,使用SpringSession踩的坑及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
一文詳解SpringBoot如何優(yōu)雅地實(shí)現(xiàn)異步調(diào)用
SpringBoot想必大家都用過，但是大家平時使用發(fā)布的接口大都是同步的，那么你知道如何優(yōu)雅的實(shí)現(xiàn)異步呢？這篇文章就來和大家詳細(xì)聊聊2023-03-03
Java 是如何讀取和寫入瀏覽器Cookies的實(shí)例詳解
這篇文章主要介紹了Java 是如何讀取和寫入瀏覽器Cookies的實(shí)例的相關(guān)資料,需要的朋友可以參考下2016-09-09
Jmeter的接口測試詳細(xì)步驟并實(shí)現(xiàn)業(yè)務(wù)閉環(huán)
這篇文章主要介紹了Jmeter的接口測試詳細(xì)步驟并實(shí)現(xiàn)業(yè)務(wù)閉環(huán)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08