歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++面試題-鏈表棧二叉樹數據結構

一、單鏈表

目錄

1.單鏈表反轉

2.找出單鏈表的倒數第4個元素

3.找出單鏈表的中間元素

4.刪除無頭單鏈表的一個節點

5.兩個不交叉的有序鏈表的合並

6.有個二級單鏈表,其中每個元素都含有一個指向一個單鏈表的指針。寫程序把這個二級鏈表稱一級單鏈表。

7.單鏈表交換任意兩個元素(不包括表頭)

8.判斷單鏈表是否有環?如何找到環的“起始”點?如何知道環的長度?

9.判斷兩個單鏈表是否相交

10.兩個單鏈表相交,計算相交點

11.用鏈表模擬大整數加法運算

12.單鏈表排序

13.刪除單鏈表中重復的元素

 

 

首先寫一個單鏈表的C#實現,這是我們的基石:

public class Link

{

public Link Next;

public string Data;

public Link(Link next, string data)

{

this.Next = next;

this.Data = data;

}

}

 

 

其中,我們需要人為地在單鏈表前面加一個空節點,稱其為head。例如,一個單鏈表是1->2->5,如圖所示:

 

 

 

對一個單鏈表的遍歷如下所示:

static void Main(string[] args)

{

Link head = GenerateLink();

Link curr = head;

while (curr != null)

{

Console.WriteLine(curr.Data);

curr = curr.Next;

}

}

 

 

1.單鏈表反轉

這道題目有兩種算法,既然是要反轉,那麼肯定是要破壞原有的數據結構的:

算法1:我們需要額外的兩個變量來存儲當前節點curr的下一個節點next、再下一個節點nextnext:

public static Link ReverseLink1(Link head)

{

Link curr = head.Next;

Link next = null;

Link nextnext = null;

//if no elements or only one element exists

if (curr == null || curr.Next == null)

{

return head;

}

//if more than one element

while (curr.Next != null)

{

next = curr.Next; //1

nextnext = next.Next; //2

next.Next = head.Next; //3

head.Next = next; //4

curr.Next = nextnext; //5

}

return head;

}

 

 

算法的核心是while循環中的5句話

 

 

我們發現,curr始終指向第1個元素。

此外,出於編程的嚴謹性,還要考慮2種極特殊的情況:沒有元素的單鏈表,以及只有一個元素的單鏈表,都是不需要反轉的。

 

 

算法2:自然是遞歸

如果題目簡化為逆序輸出這個單鏈表,那麼遞歸是很簡單的,在遞歸函數之後輸出當前元素,這樣能確保輸出第N個元素語句永遠在第N+1個遞歸函數之後執行,也就是說第N個元素永遠在第N+1個元素之後輸出,最終我們先輸出最後一個元素,然後是倒數第2個、倒數第3個,直到輸出第1個:

public static void ReverseLink2(Link head)

{

if (head.Next != null)

{

ReverseLink2(head.Next);

Console.WriteLine(head.Next.Data);

}

}

 

 

但是,現實應用中往往不是要求我們逆序輸出(不損壞原有的單鏈表),而是把這個單鏈表逆序(破壞型)。這就要求我們在遞歸的時候,還要處理遞歸後的邏輯。

首先,要把判斷單鏈表有0或1個元素這部分邏輯獨立出來,而不需要在遞歸中每次都比較一次:

public static Link ReverseLink3(Link head)

{

//if no elements or only one element exists

if (head.Next == null || head.Next.Next == null)

return head;

head.Next = ReverseLink(head.Next);

return head;

}

 

 

我們觀測到:

head.Next = ReverseLink(head.Next);

這句話的意思是為ReverseLink方法生成的逆序鏈表添加一個空表頭。

接下來就是遞歸的核心算法ReverseLink了:

static Link ReverseLink(Link head)

{

if (head.Next == null)

return head;

Link rHead = ReverseLink(head.Next);

head.Next.Next = head;

head.Next = null;

return rHead;

}

 

 

算法的關鍵就在於遞歸後的兩條語句:

head.Next.Next = head; //1

head.Next = null; //2

啥意思呢?畫個圖表示就是:

 

 

這樣,就得到了一個逆序的單鏈表,我們只用到了1個額外的變量rHead。

Copyright © Linux教程網 All Rights Reserved