APS105预习 - 13

Question 1 Reorder

Question

**题目简述: ** 将链表所有0节点提至开头，保持非0节点顺序不变，不可以拷贝或更改节点内容（双链表拼接法不可用）

Write a C function called reorder, the prototype of which is given below, that reorders the nodes in a linked list such that nodes with a value of appear at the front of the linked list and nodes with any other integer value appear at the end of the linked list, while maintaining the original order of non-zero nodes.

Example 1:

Input List:        0   0  15   0   0  13  10
Output List:       0   0   0   0  15  13  10

Example 2:

Input List:        1   0  19   0   0   5  0
Output List:       0   0   0   0   1  19  5

Note: You are not allowed to copy or modify the data member in any of the nodes in the linked list. However, you can modify the next pointer in the nodes.

Answer

void reorder(LinkedList *list) {
  Node *current = list->head;
  Node *prev = NULL;
  while (current != NULL) {
    if (current == list->head) {
      prev = current;
      current = current->next;
    } else {
      if (current->data == 0) {
        prev->next = current->next;
        Node *oldHead = list->head;
        list->head = current;
        list->head->next = oldHead;
        current = prev->next;
      } else {
        prev = current;
        current = current->next;
      }
    }
  }
}

思路

核心思路是“将所有为0的节点删除后添加至链表开头”，但是具体实现仍有一些细节问题。第一，为了同时实现遍历链表的每一个元素和删除节点功能，需要正确维护两个遍历指针， 当前节点*current和前驱节点*prev。

第二，第一个节点是需要跳过的，它的值是否为0不重要

第三， 当一个节点为0，且执行过删除再插入的操作之后，只需要更新current指针