中間鏈表

Question

如何找到鏈表的中間，當我們沒有被告知它的大小，它必須只使用一個循環，只有一個指針來進行的。

Answer 1

約

LinkedList * llist = getLList(); // the linked list 
Node * node = llist.head; 

while (node) { 
    node = node.next; 
    if (node) { 
     node = node.next; 
     llist.remove(llist.head); 
    } 
} 
// now llist.head is (er, um... was) the middle node. 
// hope you didn't need the rest of the list. 

Answer 2

Node *m,*e,*head; /* head is given */ 
m=e=head; 
while(e) { 
    e=e->next; 
    if (e) { 
    e=e->next; 
    m=m->next; 
    } 
} 
/* now m is the middle node */ 

對不起，我不得不用兩個指針:)

---

添加給你的答案，因爲一個小調整降低指針的數量爲1。我希望你不介意：

Node m,*e,*head; /* head is given */ 
e = head; 
if (e) m = *e; 
while(e) { 
    e = e->next; 
    if (e) { 
    e = e->next; 
    m = *(m.next); 
    } 
} 
/* now m is the middle node */ 

Answer 3

嗯，這是一種破解，因爲它在功能上等同於2個循環。但是，它仍然只有1個循環。

Node* middle(Node* const begin) 
{ 
    Node* current = begin; 
    bool size_known = false; 
    int size = 0; 
    while (true) 
    { 
     if (!size_known) 
     { 
      if (current) 
      { 
       ++size; 
       current = current->next; 
      } 
      else 
      { 
       current = begin; 
       size_known = true; 
      } 
     } 
     else 
     { 
      if (size <= 1) 
       return current; 
      current = current->next; 
      size -= 2; 
     } 
    } 
} 

Answer 4

怎麼看我的代碼。它適用於我的FC9 x86_64的正確，功能「中間（）」是你想要什麼：

static struct node *middle(struct node *head) 
{ 
     struct node *mid = head; 
     int flag = 0; 
     while (NULL != head) { 
       head = head->next; 
       flag = !flag; 
       if (flag) { 
         mid = mid->next; 
       } 
     } 
     return mid; 
} 

編輯：刪除代碼，除了中間的（）。

Answer 5

使用提供的頭指針對列表進行迭代，然後增加一個允許的指針（我假設您的模糊問題是允許一個指針除了傳入的指針）每兩個增量的頭指針。

Node* middle(Node* head) 
{ 
    Node* middle = head; 
    while (head != NULL) { 
     head = head->next; 

     if (head->next != NULL) { 
      head = head->next; 
      middle = middle->next; 
     } 
    } 
    return middle; 
} 

這裏有一些邊緣情況被忽略（比如什麼是偶數個元素的列表中間）。

Answer 6

我們可以在這種情況下使用跳躍列表：

1）在鏈表遍歷每個節點使奇數節點的跳躍列表。時間：O（n）的空間：O（N/2）

2）現在，當你到達列表的末尾除以2 legnth加1得到中間元素的索引。

3）搜索在跳躍列表O（LOGN）時間的索引。

因此，該算法的總的時間複雜是：

爲O（n）（1個遍歷）+ O（LOGN）（搜索跳轉列表）= O（n）的 空間複雜度：O（N/2）

請回復，如果這是低效....

Answer 7

我在IBM ISL浦那類似的問題。問：「如何查找單鏈表的中間節點」。 我回答 答：「拿兩根指針開始在頭部和移動在一步一個指針，並在兩個步驟的另一指針」。採訪者說，這是最簡單的解決方案。問：告訴我你將如何遍歷而不使用2個指針。提示是「使用編譯器屬性」。

有誰知道如何使用編譯器屬性查找中間節點？