Java單連結清單面試題
做面試題之前，我們先完善單連結清單類，之前做的沒有貫徹面向對象、封裝的思想。
新的節點類：
public class HeroNode {
private int id;
private String name;
private HeroNode next;
public HeroNode(int id, String name) {
this.id = id;
this.name = name;
}
public HeroNode() {
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getNext() {
return next;
}
public void setNext(HeroNode next) {
this.next = next;
}
@Override
public String toString() {
return "HeroNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
新的單連結清單類：
package datastru;
public class MySingleLinkedList {
private HeroNode head;
public MySingleLinkedList(HeroNode head) {
this.head = head;
}
public MySingleLinkedList() {
}
public HeroNode getHead() {
return head;
}
public void setHead(HeroNode head) {
this.head = head;
}
// 周遊
public void list(){
HeroNode currentNode = head.getNext();
if (currentNode == null)
System.out.println("連結清單空!");
while (currentNode != null){
System.out.println(currentNode);
currentNode = currentNode.getNext();
}
}
// 在末尾添加
public void add(HeroNode heroNodeForAdd){
HeroNode currentNode = head;
while (currentNode.getNext() != null){
currentNode = currentNode.getNext();
}
currentNode.setNext(heroNodeForAdd);
}
// 按id查找，傳回該節點
public HeroNode searchById(int idForSearch){
HeroNode currentNode = head.getNext();
while (currentNode != null){
if (currentNode.getId() == idForSearch){
return currentNode;
}
currentNode = currentNode.getNext();
}
return currentNode;
}
// 按id删除
public void deleteById(int idForDelete){
HeroNode currentNode = head;
while (currentNode.getNext() != null){
if (currentNode.getNext().getId() == idForDelete)
currentNode.setNext(currentNode.getNext().getNext());
currentNode = currentNode.getNext();
}
}
}
注意：單連結清單中我手寫的四個方法也有可能出現在面試裡。
擷取單連結清單長度
// 擷取單連結清單長度
public int getLength(){
int length = 0;
HeroNode currentNode = head.getNext();
while (currentNode != null){
length++;
currentNode = currentNode.getNext();
}
return length;
}
查找單連結清單倒數第k個元素
該需求還有更優的實作方法，後面講！
// 查找單連結清單倒數第k個元素
public HeroNode searchByK(int k){
int length = getLength(); // 擷取長度
HeroNode currentNode = head.getNext();
for (int i = 0; i < length - k; i++){
currentNode = currentNode.getNext();
}
return currentNode;
}
單連結清單反轉
// 單連結清單反轉
public void reverse(){
HeroNode currentNode = head.getNext();
HeroNode nextNode = currentNode;
HeroNode reverseHead = new HeroNode();
while(currentNode != null){
nextNode = nextNode.getNext();
currentNode.setNext(reverseHead.getNext());
reverseHead.setNext(currentNode);
currentNode = nextNode;
}
head = reverseHead;
}
反向列印單連結清單（不破壞原有單連結清單）
// 反向列印單連結清單（不破壞原有單連結清單）
public void printReverse(){
StringBuilder str = new StringBuilder();
HeroNode currentNode = head.getNext();
while(currentNode != null){
str = str.insert(0,currentNode.toString() + "\n");
currentNode = currentNode.getNext();
}
System.out.println(str);
}
測試
public static void main(String[] args) {
MySingleLinkedList mySingleLinkedList = new MySingleLinkedList();
mySingleLinkedList.setHead(new HeroNode());
// 周遊
mySingleLinkedList.list();
// 插入測試
System.out.println("插入測試：");
mySingleLinkedList.add(new HeroNode(1,"亞瑟"));
mySingleLinkedList.add(new HeroNode(3,"妲己"));
mySingleLinkedList.add(new HeroNode(5,"魯班"));
mySingleLinkedList.add(new HeroNode(7,"莊周"));
mySingleLinkedList.add(new HeroNode(9,"狂鐵"));
mySingleLinkedList.add(new HeroNode(11,"後羿"));
mySingleLinkedList.add(new HeroNode(13,"韓信"));
mySingleLinkedList.list();
// 查找測試
System.out.println("查找id = 9：");
System.out.println(mySingleLinkedList.searchById(9).toString());
// 删除測試
mySingleLinkedList.deleteById(5);
System.out.println("根據id = 5 進行删除結果：");
mySingleLinkedList.list();
// 擷取單連結清單長度
System.out.print("擷取單連結清單長度：");
System.out.println(mySingleLinkedList.getLength());
// 查找單連結清單倒數第k個元素
System.out.println("查找單連結清單倒數第3個元素：");
System.out.println(mySingleLinkedList.searchByK(3).toString());
// 反向列印單連結清單（不破壞原有單連結清單）
System.out.println("反向列印單連結清單：");
mySingleLinkedList.printReverse();
// 單連結清單反轉
System.out.println("單連結清單反轉：");
mySingleLinkedList.reverse();
mySingleLinkedList.list();
}
測試結果：
連結清單空!
插入測試：
HeroNode{id=1, name=‘亞瑟’}
HeroNode{id=3, name=‘妲己’}
HeroNode{id=5, name=‘魯班’}
HeroNode{id=7, name=‘莊周’}
HeroNode{id=9, name=‘狂鐵’}
HeroNode{id=11, name=‘後羿’}
HeroNode{id=13, name=‘韓信’}
查找id = 9：
HeroNode{id=9, name=‘狂鐵’}
根據id = 5 進行删除結果：
HeroNode{id=1, name=‘亞瑟’}
HeroNode{id=3, name=‘妲己’}
HeroNode{id=7, name=‘莊周’}
HeroNode{id=9, name=‘狂鐵’}
HeroNode{id=11, name=‘後羿’}
HeroNode{id=13, name=‘韓信’}
擷取單連結清單長度：6
查找單連結清單倒數第3個元素：
HeroNode{id=9, name=‘狂鐵’}
反向列印單連結清單：
HeroNode{id=13, name=‘韓信’}
HeroNode{id=11, name=‘後羿’}
HeroNode{id=9, name=‘狂鐵’}
HeroNode{id=7, name=‘莊周’}
HeroNode{id=3, name=‘妲己’}
HeroNode{id=1, name=‘亞瑟’}
單連結清單反轉：
HeroNode{id=13, name=‘韓信’}
HeroNode{id=11, name=‘後羿’}
HeroNode{id=9, name=‘狂鐵’}
HeroNode{id=7, name=‘莊周’}
HeroNode{id=3, name=‘妲己’}
HeroNode{id=1, name=‘亞瑟’}
---------------------------------------------------------
面試題擴充
新查找單連結清單倒數第k個元素
上邊的查找單連結清單倒數第k個元素需要先擷取長度length，再去周遊length - k次，擷取長度需要周遊一遍的，總共周遊兩次，其實還有一種新的方法。
設定兩個引用（指針），一個叫first先走k次，然後和第二個second一起走，直到first走到最後的時候，second就走到了倒數第k的位置。
// 查找單連結清單倒數第k個元素
public HeroNode searchByK1(int k){
HeroNode first = head.getNext();
HeroNode second= head.getNext();
for (int i = 0; i < k; i++) {
first = first.getNext();
}
while (first != null){
first = first.getNext();
second = second.getNext();
}
return second;
}
合并兩個有序的單連結清單，合并後依然有序
單連結清單實作約瑟夫環
單連結清單排序
查找單連結清單的中間節點，要求隻能周遊一次連結清單
判斷單連結清單是否帶環？若帶環，求環的長度？求環的入口點？
判斷兩個連結清單是否相交，若相交，求交點。（假設連結清單不帶環）
複雜連結清單的複制。
删除無序清單重的重複元素
連結清單相加求和
重排連結清單
銷毀連結清單
如何将排序清單轉化為二分查找樹？
給定一個連結清單和一個特定值 x，對連結清單進行分隔，使得所有小于 x 的節點都在大于或等于 x 的節點之前。
未完待續…
![2017年團體程式設計天梯賽-決賽小結[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)