現(xiàn)在有一個(gè)單向鏈表邀杏，談一談贫奠，如何判斷鏈表中是否出現(xiàn)了環(huán)
考察點(diǎn)：鏈表
參考回答：
單鏈表有環(huán)，是指單鏈表中某個(gè)節(jié)點(diǎn)的next指針域指向的是鏈表中在它之前的某一個(gè)節(jié)點(diǎn)，這樣在鏈表的尾部形成一個(gè)環(huán)形結(jié)構(gòu)叮阅。
// 鏈表的節(jié)點(diǎn)結(jié)構(gòu)如下 typedef struct node { int data; struct node *next; } NODE;
最常用方法：定義兩個(gè)指針刁品，同時(shí)從鏈表的頭節(jié)點(diǎn)出發(fā)，一個(gè)指針一次走一步浩姥，另一個(gè)指針一次走兩步挑随。如果走得快的指針追上了走得慢的指針，那么鏈表就是環(huán)形鏈表勒叠；如果走得快的指針走到了鏈表的末尾（next指向 NULL）都沒(méi)有追上第一個(gè)指針兜挨，那么鏈表就不是環(huán)形鏈表。
通過(guò)使用STL庫(kù)中的map表進(jìn)行映射眯分。首先定義 map<NODE *, int> m; 將一個(gè) NODE * 指針映射成數(shù)組的下標(biāo)拌汇，并賦值為一個(gè) int 類型的數(shù)值。然后從鏈表的頭指針開(kāi)始往后遍歷弊决，每次遇到一個(gè)指針p噪舀，就判斷 m[p] 是否為0。如果為0飘诗，則將m[p]賦值為1与倡，表示該節(jié)點(diǎn)第一次訪問(wèn)；而如果m[p]的值為1昆稿，則說(shuō)明這個(gè)節(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)一次了纺座，于是就形成了環(huán)。
談一談溉潭，bucket如果用鏈表存儲(chǔ)净响，它的缺點(diǎn)是什么？
考察點(diǎn)：鏈表
參考回答：
①查找速度慢喳瓣，因?yàn)椴檎視r(shí)馋贤，需要循環(huán)鏈表訪問(wèn)
②如果進(jìn)行頻繁插入和刪除操作，會(huì)導(dǎo)致速度很慢畏陕。
有一個(gè)鏈表掸掸，奇數(shù)位升序偶數(shù)位降序，如何將鏈表變成升序
考察點(diǎn)：鏈表
參考回答：
public class
OddIncreaseEvenDecrease {
/**
* 按照奇偶位拆分成兩個(gè)鏈表
* @param head
* @return
*/
public static Node[] getLists(Node head){
Node head1 = null;
Node head2 = null;
Node cur1 = null;
Node cur2 = null;
int count = 1;//用來(lái)計(jì)數(shù)
while(head != null){
if(count % 2 == 1){
if(cur1 != null){
cur1.next = head;
cur1 = cur1.next;
}else{
cur1 = head;
head1 = cur1;
}
}else{
if(cur2 != null){
cur2.next = head;
cur2 = cur2.next;
}else{
cur2 = head;
head2 = cur2;
}
}
head = head.next;
count++;
}
//跳出循環(huán)蹭秋，要讓最后兩個(gè)末尾元素的下一個(gè)都指向null
cur1.next = null;
cur2.next = null;
Node[] nodes = new Node[]{head1,
head2};
return nodes;
}
/**
* 反轉(zhuǎn)鏈表
* @param head
* @return
*/
public static Node reverseList(Node head){
Node pre = null;
Node next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
/**
* 合并兩個(gè)有序鏈表
* @param head1
* @param head2
* @return
*/
public static Node CombineList(Node head1,
Node head2){
if(head1 == null || head2 == null){
return head1 != null ? head1 :
head2;
}
Node head = head1.value < head2.value ?
head1 : head2;
Node cur1 = head == head1 ? head1 :
head2;
Node cur2 = head == head1 ? head2 :
head1;
Node pre = null;
Node next = null;
while(cur1 != null && cur2 !=
null){
if(cur1.value <= cur2.value){//這里一定要有=，否則一旦cur1的value和cur2的value相等的話堤撵，下面的pre.next會(huì)出現(xiàn)空指針異常
pre = cur1;
cur1 = cur1.next;
}else{
next = cur2.next;
pre.next = cur2;
cur2.next = cur1;
pre = cur2;
cur2 = next;
}
}
pre.next = cur1 == null ? cur2 : cur1;
return head;
}
}
隨機(jī)鏈表的復(fù)制
考察點(diǎn)：鏈表
參考回答：
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
RandomListNode p = head;
// copy every node and insert to list
while (p != null) {
RandomListNode copy = new RandomListNode(p.label);
copy.next = p.next;
p.next = copy;
p = copy.next;
}
// copy random pointer for each new node
p = head;
while (p != null) {
if (p.random != null)
p.next.random = p.random.next;
p = p.next.next;
}
// break list to two
p = head;
RandomListNode newHead = head.next;
while (p != null) {
RandomListNode temp = p.next;
p.next = temp.next;
if (temp.next != null)
temp.next = temp.next.next;
p = p.next;
}
return newHead;
}
如何反轉(zhuǎn)單鏈表
考察點(diǎn)：鏈表
參考回答：
ListNode
reverseList(ListNode* head) {
if(head == nullptr || head->next ==
nullptr)
return head;
ListNode* p;
ListNode* q;
ListNode* r;
p = head;
q = head->next;
head->next = nullptr;//舊的頭指針是新的尾指針 指向NULL
while(q){
r = q->next;//用來(lái)保存下一步要處理的指針
q->next = p;//p q 交替處理 進(jìn)行反轉(zhuǎn)單鏈表
p = q;
q = r;
}
head = p;//最后的q必定指向NULL仁讨，p就成了新鏈表的頭指針
return head;
}
