国产BBAAAAA片,韩国爱情电影在线完整版,在线无码中文字幕一区,无码免费人妻A片AAA毛片西瓜,国产亚洲精品久久777777黑寡妇,农村熟妇高潮精品A片,性做爰1一7伦,成人片黄网站色大片免费毛片,少妇搡BBBB搡BBB搡野外,国产偷人妻精品一区

這篇文章包含的鏈表面試題如下：

1、從尾到頭打印單向鏈表

2、查找單向鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)

3、反轉(zhuǎn)一個(gè)單向鏈表【出現(xiàn)頻率較高】

4、合并兩個(gè)有序的單向鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率較高】

5、找出兩個(gè)單向鏈表相交的個(gè)公共節(jié)點(diǎn)

前期代碼準(zhǔn)備： 
下面這兩個(gè)類的詳細(xì)解析可以參考我的上一篇文章：數(shù)據(jù)結(jié)構(gòu)3 線性表之鏈表

節(jié)點(diǎn)類：Node.java

/** 
* 節(jié)點(diǎn)類 
*/ 
public class Node { 
Object element; // 數(shù)據(jù)域 
Node next; // 地址域

// 節(jié)點(diǎn)的構(gòu)造方法
public Node(Object element, Node next) {
    this.element = element;
    this.next = next;
}

// Gettet and Setter
public Node getNext() {
    return this.next;
}

public void setNext(Node next) {
    this.next = next;
}

public Object getElement() {
    return this.element;
}

public void setElement(Object element) {
    this.element = element;
} 

}

鏈表類：MyLinkedList.java

/** 
* 自己定義的一個(gè)鏈表類 
*/ 
public class MyLinkedList {

// 頭節(jié)點(diǎn)
private Node headNode;
// 用來遍歷鏈表的臨時(shí)節(jié)點(diǎn)
private Node tempNode;

// Getter
public Node getHeadNode() {
    return headNode;
}
// Setter
public void setHeadNode(Node headNode) {
    this.headNode = headNode;
}

// 鏈表的初始化方法
public MyLinkedList() {
    // 初始化時(shí)，鏈表里面只有1個(gè)節(jié)點(diǎn)，所以這個(gè)節(jié)點(diǎn)的地址域?yàn)閚ull
    Node node = new Node("王重陽", null);
    // 頭節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，它的數(shù)據(jù)域?yàn)閚ull，它的地址域存儲(chǔ)了第1個(gè)節(jié)點(diǎn)的地址
    headNode = new Node(null, node);
}

/**
 * 1、插入節(jié)點(diǎn)：時(shí)間復(fù)雜度為O(n)
 * @param newNode 需要插入的新節(jié)點(diǎn)
 * @param position 這個(gè)變量的范圍可以從0到鏈表的長度，注意不要越界。
 *                 頭節(jié)點(diǎn)不算進(jìn)鏈表的長度，
 *                 所以從頭節(jié)點(diǎn)后面的節(jié)點(diǎn)開始算起，position為0
 */
public void insert(Node newNode, int position) {
    // 通過position變量，讓tempNode節(jié)點(diǎn)從頭節(jié)點(diǎn)開始遍歷，移動(dòng)到要插入位置的前一個(gè)位置
    tempNode = headNode;
    int i = 0;
    while (i < position) {
        tempNode = tempNode.next;
        i++;
    }
    newNode.next = tempNode.next;
    tempNode.next = newNode;
}

/**
 * 2、刪除節(jié)點(diǎn)：時(shí)間復(fù)雜度為O(n)
 * @param position
 */
public void delete(int position) {
    // 這里同樣需要用tempNode從頭開始向后查找position
    tempNode = headNode;
    int i = 0;
    while (i < position) {
        tempNode = tempNode.next;
        i++;
    }
    tempNode.next = tempNode.next.next;
}

/**
 * 3、查找節(jié)點(diǎn)：時(shí)間復(fù)雜度為O(n)
 * @param position
 * @return 返回查找的節(jié)點(diǎn)
 */
public Node find(int position) {
    // 這里同樣需要用tempNode從頭開始向后查找position
    tempNode = headNode;
    int i = 0;
    while (i < position) {
        tempNode = tempNode.next;
        i++;
    }
    return tempNode.next;
}

/**
 * 4、獲取鏈表的長度：時(shí)間復(fù)雜度為O(n)
 * @return
 */
public int size() {
    tempNode = headNode.next;
    int size = 0;
    while (tempNode.next != null) {
        size = size + 1;
        tempNode = tempNode.next;
    }
    size = size + 1; // tempNode的地址域?yàn)閚ull時(shí)，size記得加上后一個(gè)節(jié)點(diǎn)
    return size;
}

// 遍歷鏈表，打印出所有節(jié)點(diǎn)的方法
public void showAll() {
    tempNode = headNode.next;
    while (tempNode.next != null) {
        System.out.println(tempNode.element);
        tempNode = tempNode.next;
    }
    System.out.println(tempNode.element);
} 

}

1、從尾到頭打印單向鏈表 
對(duì)于這種顛倒順序打印的問題，我們應(yīng)該就會(huì)想到棧，后進(jìn)先出。因此這一題要么自己新建一個(gè)棧，要么使用系統(tǒng)的棧（系統(tǒng)遞歸調(diào)用方法時(shí)的棧）。需要把鏈表遍歷完一次，所以它的時(shí)間復(fù)雜度為 O(n)

注意：不能先把鏈表反轉(zhuǎn)，再遍歷輸出，因?yàn)檫@樣做會(huì)破壞鏈表節(jié)點(diǎn)原來的順序。

方法1：自己新建一個(gè)棧

QuestionOneDemo.java

import org.junit.Test;

import java.util.Stack;

public class QuestionOneDemo {

/**
 * 從尾到頭打印單向鏈表
 * 方法1：自己新建一個(gè)棧
 *
 * @param head 參數(shù)為鏈表的頭節(jié)點(diǎn)
 */
public void reversePrint(Node head) {

    // 判斷鏈表是否為空
    if (head == null) {
        return;
    }

    // 新建一個(gè)棧
    Stack<Node> stack = new Stack<Node>();

    // 用來遍歷的臨時(shí)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始
    Node tempNode = head;

    // 從頭節(jié)點(diǎn)開始遍歷鏈表，將除了頭節(jié)點(diǎn)之外的所有節(jié)點(diǎn)壓棧
    while (tempNode.getNext() != null) {
        tempNode = tempNode.getNext();
        stack.push(tempNode);
    }

    // 將棧中的節(jié)點(diǎn)打印輸出即可
    while (stack.size() > 0) {
        // 出棧操作
        Node node = stack.pop();
        System.out.println(node.getElement());
    }
}

/**
 * 用來測(cè)試的方法
 */
@Test
public void test() {
    MyLinkedList myLinkedList = new MyLinkedList();

    Node newNode1 = new Node("歐陽鋒", null);
    Node newNode2 = new Node("黃藥師", null);
    Node newNode3 = new Node("洪七公", null);

    myLinkedList.insert(newNode1, 1);
    myLinkedList.insert(newNode2, 2);
    myLinkedList.insert(newNode3, 3);

    System.out.println("----原鏈表 start----");
    myLinkedList.showAll();
    System.out.println("----原鏈表 end----");
    System.out.println("");

    System.out.println("====從尾到頭打印鏈表 start====");
    reversePrint(myLinkedList.getHeadNode());
    System.out.println("====從尾到頭打印鏈表 end====");
    System.out.println("");

    System.out.println("----原鏈表(依然保留了原來的順序) start----");
    myLinkedList.showAll();
    System.out.println("----原鏈表(依然保留了原來的順序) end----");

} 

}

測(cè)試結(jié)果：

方法2：使用系統(tǒng)的棧（遞歸）

在 QuestionOneDemo.java 中添加方法2

/**
 * 從尾到頭打印單向鏈表
 * 方法2：自己新建一個(gè)棧
 *
 * @param head 參數(shù)為鏈表的頭節(jié)點(diǎn)
 */
public void reversePrint2(Node head) {

    // 判斷傳進(jìn)來的參數(shù)節(jié)點(diǎn)是否為空
    if (head == null) {
        return;
    }

    // 遞歸
    reversePrint2(head.next);
    System.out.println(head.getElement());
} 

測(cè)試的方法和測(cè)試結(jié)果跟方法1一樣，這里不再詳細(xì)列出。

總結(jié)：

方法2是基于遞歸實(shí)現(xiàn)的，代碼看起來更簡潔，但有一個(gè)問題：當(dāng)鏈表很長的時(shí)候，就會(huì)導(dǎo)致方法調(diào)用的層級(jí)很深，有可能造成棧溢出。而方法1是自己新建一個(gè)棧，使用循環(huán)壓棧和循環(huán)出棧，代碼的穩(wěn)健性要更好一些。

2、查找單向鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn) 
2-1：普通思路

先將整個(gè)鏈表從頭到尾遍歷一次，計(jì)算出鏈表的長度size，得到鏈表的長度之后，就好辦了，直接輸出第 size-k 個(gè)節(jié)點(diǎn)就可以了（注意鏈表為空，k為0，k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)的情況）。因?yàn)樾枰闅v兩次鏈表，所以時(shí)間復(fù)雜度為 T(2n) = O(n)

代碼如下：

QuestionTwoDemo.java

import org.junit.Test;

public class QuestionTwoDemo {

/**
 * 查找鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)的方法
 *
 * @param myLinkedList 需要查找的鏈表作為參數(shù)傳遞進(jìn)來
 * @param k            代表倒數(shù)第k個(gè)節(jié)點(diǎn)的位置
 * @return
 */
public Node reciprocalFindNode(MyLinkedList myLinkedList, int k) throws Exception {
    int size = 0;

    // 如果頭節(jié)點(diǎn)為null，說明鏈表為空
    if (myLinkedList.getHeadNode() == null) {
        throw new Exception("鏈表為空");
    }

    // 判斷k，k不能為0
    if (k == 0) {
        throw new Exception("k不能為0");
    }

    // 次遍歷，計(jì)算出鏈表的長度size
    Node tempNode = myLinkedList.getHeadNode();
    while (tempNode != null) {
        size++;
        tempNode = tempNode.getNext();
    }

    // 判斷k，k不能大于鏈表中節(jié)點(diǎn)的個(gè)數(shù)
    if (k > size) {
        throw new Exception("k不能大于鏈表中節(jié)點(diǎn)的個(gè)數(shù)");
    }

    // 第二次遍歷，找出倒數(shù)第k個(gè)節(jié)點(diǎn)
    tempNode = myLinkedList.getHeadNode();
    for (int i = 0; i < size - k; i++) {
        tempNode = tempNode.getNext();
    }
    return tempNode;
}

/**
 * 用來測(cè)試的方法
 */
@Test
public void test() throws Exception {
    MyLinkedList myLinkedList = new MyLinkedList();

    Node newNode1 = new Node("歐陽鋒", null);
    Node newNode2 = new Node("黃藥師", null);
    Node newNode3 = new Node("洪七公", null);

    myLinkedList.insert(newNode1, 1);
    myLinkedList.insert(newNode2, 2);
    myLinkedList.insert(newNode3, 3);

    System.out.println("-----完整的鏈表start-----");
    myLinkedList.showAll();
    System.out.println("-----完整的鏈表end-------");
    System.out.println("");

    Node node = reciprocalFindNode(myLinkedList, 1);
    System.out.println("鏈表的倒數(shù)第1個(gè)節(jié)點(diǎn)是：" + node.getElement());

    node = reciprocalFindNode(myLinkedList, 2);
    System.out.println("鏈表的倒數(shù)第2個(gè)節(jié)點(diǎn)是：" + node.getElement());

    node = reciprocalFindNode(myLinkedList, 3);
    System.out.println("鏈表的倒數(shù)第3個(gè)節(jié)點(diǎn)是：" + node.getElement());

    node = reciprocalFindNode(myLinkedList, 4);
    System.out.println("鏈表的倒數(shù)第4個(gè)節(jié)點(diǎn)是：" + node.getElement());
} 

}

測(cè)試結(jié)果：

如果面試官不允許你遍歷鏈表的長度，該怎么做？接下來的改進(jìn)思路就是。

2-2：改進(jìn)思路

這里需要用到兩個(gè)節(jié)點(diǎn)型的變量：即變量 first 和 second，首先讓 first 和 second 都指向個(gè)節(jié)點(diǎn)，然后讓 second 節(jié)點(diǎn)往后挪 k-1 個(gè)位置，此時(shí) first 和 second 就間隔了 k-1 個(gè)位置，然后整體向后移動(dòng)這兩個(gè)節(jié)點(diǎn)，直到 second 節(jié)點(diǎn)走到后一個(gè)節(jié)點(diǎn)時(shí)，此時(shí) first 節(jié)點(diǎn)所指向的位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)的位置。時(shí)間復(fù)雜度為O(n)

步驟一：

步驟二：

步驟三：

代碼：

在 QuestionTwoDemo.java 中添加方法

/**
 * 查找鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)的方法2
 *
 * @param myLinkedList 需要查找的鏈表作為參數(shù)傳遞進(jìn)來
 * @param k            代表倒數(shù)第k個(gè)節(jié)點(diǎn)的位置
 * @return
 */
public Node reciprocalFindNode2(MyLinkedList myLinkedList, int k) throws Exception {
    // 如果頭節(jié)點(diǎn)為null，說明鏈表為空
    if (myLinkedList.getHeadNode() == null) {
        throw new Exception("鏈表為空");
    }

    Node first = myLinkedList.getHeadNode();
    Node second = myLinkedList.getHeadNode();

    // 讓second節(jié)點(diǎn)往后挪 k-1 個(gè)位置
    for (int i = 0; i < k - 1; i++) {
        second = second.getNext();
    }

    // 讓first節(jié)點(diǎn)和second節(jié)點(diǎn)整體向后移動(dòng)，直到second節(jié)點(diǎn)走到后一個(gè)節(jié)點(diǎn)
    while (second.getNext() != null) {
        first = first.getNext();
        second = second.getNext();
    }
    // 當(dāng)second節(jié)點(diǎn)走到后一個(gè)節(jié)點(diǎn)時(shí)，first節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)
    return first;
} 

測(cè)試的方法和測(cè)試結(jié)果跟前面的一樣，這里不再詳細(xì)列出。

3、反轉(zhuǎn)一個(gè)單向鏈表 
例如鏈表：

1 -> 2 -> 3 -> 4

反轉(zhuǎn)之后：

4 -> 3 -> 2 -> 1

思路：

從頭到尾遍歷原鏈表的節(jié)點(diǎn)，每遍歷一個(gè)節(jié)點(diǎn)，將它放在新鏈表（實(shí)際上并沒有創(chuàng)建新鏈表，這里用新鏈表來描述只是為了更方便的理解）的前端。 時(shí)間復(fù)雜度為O(n)

（注意鏈表為空和只有一個(gè)節(jié)點(diǎn)的情況）

示意圖一：

示意圖二：

示意圖三：

如此類推。。。

代碼如下：

QuestionThreeDemo.java

import org.junit.Test;

public class QuestionThreeDemo {

/**
 * 反轉(zhuǎn)一個(gè)單向鏈表的方法
 *
 * @param myLinkedList
 * @throws Exception
 */
public void reverseList(MyLinkedList myLinkedList) throws Exception {
    // 判斷鏈表是否為null
    if (myLinkedList == null || myLinkedList.getHeadNode() == null || myLinkedList.getHeadNode().getNext() == null) {
        throw new Exception("鏈表為空");
    }

    // 判斷鏈表里是否只有一個(gè)節(jié)點(diǎn)
    if (myLinkedList.getHeadNode().getNext().getNext() == null) {
        // 鏈表里只有一個(gè)節(jié)點(diǎn)，不用反轉(zhuǎn)
        return;
    }

    // tempNode 從頭節(jié)點(diǎn)后面的個(gè)節(jié)點(diǎn)開始往后移動(dòng)
    Node tempNode = myLinkedList.getHeadNode().getNext();
    // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    Node nextNode = null;
    // 反轉(zhuǎn)后新鏈表的頭節(jié)點(diǎn)
    Node newHeadNode = null;

    // 遍歷鏈表，每遍歷到一個(gè)節(jié)點(diǎn)都把它放到鏈表的頭節(jié)點(diǎn)位置
    while (tempNode.getNext() != null) {
        // 把tempNode在舊鏈表中的下一個(gè)節(jié)點(diǎn)暫存起來
        nextNode = tempNode.getNext();
        // 設(shè)置tempNode在新鏈表中作為頭節(jié)點(diǎn)的next值
        tempNode.setNext(newHeadNode);
        // 更新newHeadNode的值，下一次循環(huán)需要用
        newHeadNode = tempNode;
        // 更新頭節(jié)點(diǎn)
        myLinkedList.setHeadNode(newHeadNode);
        // tempNode往后移動(dòng)一個(gè)位置
        tempNode = nextNode;
    }
    // 舊鏈表的后一個(gè)節(jié)點(diǎn)的next為null，要把該節(jié)點(diǎn)的next設(shè)置為新鏈表的第二個(gè)節(jié)點(diǎn)
    tempNode.setNext(newHeadNode);
    // 然后把它放到新鏈表的個(gè)節(jié)點(diǎn)的位置
    myLinkedList.setHeadNode(tempNode);
    // 新建一個(gè)新鏈表的頭節(jié)點(diǎn)
    newHeadNode = new Node(null, tempNode);
    myLinkedList.setHeadNode(newHeadNode);
}

/**
 * 用來測(cè)試的方法
 */
@Test
public void test() throws Exception {
    MyLinkedList myLinkedList = new MyLinkedList();

    Node newNode1 = new Node("歐陽鋒", null);
    Node newNode2 = new Node("黃藥師", null);
    Node newNode3 = new Node("洪七公", null);

    myLinkedList.insert(newNode1, 1);
    myLinkedList.insert(newNode2, 2);
    myLinkedList.insert(newNode3, 3);

    System.out.println("-----完整的鏈表start-----");
    myLinkedList.showAll();
    System.out.println("-----完整的鏈表end-------");
    System.out.println("");

    System.out.println("-----反轉(zhuǎn)之后的鏈表start-----");
    reverseList(myLinkedList);
    myLinkedList.showAll();
    System.out.println("-----反轉(zhuǎn)之后的鏈表end-------");
} 

}

測(cè)試結(jié)果：

4、合并兩個(gè)有序的單向鏈表，合并之后的鏈表依然有序

5、找出兩個(gè)單向鏈表相交的個(gè)公共節(jié)