c - 添加到链表的尾部而不使用 if

Question

这是一个面试问题，我想我会和你们分享。

如何在不使用“if”的情况下有效地添加到链表的尾部？

从此函数中删除 if。(?仍然是if)。

typedef struct tNode_ tNode;

struct tNode_ {
  tNode* pNext;
  int data;
};

tNode* pHead = NULL;
tNode* pTail = NULL;   

AddTail(tNode* pNode){
  if(!pTail) {
    pHead = pNode;
  }
  else {
    pTail->pNext = pNode;
  }
  pTail = pNode;
  pTail->pNext = NULL;
}

Answer 1

一种（诚然愚蠢的）方法是使用短路逻辑运算符&&和||. 例如，您可以这样做：

  AddTail(tNode* pNode){
      pTail || (pHead = pNode);
      !pTail || (pTail->pNext = pNode);

      pTail = pNode;
      pTail->pNext = NULL;
 }

这是有效的，因为如果ptail为 null，则第一条语句的第一部分将评估为 false，从而强制评估语句的后半部分||。如果它不为空，则不会评估语句的后半部分。类似的逻辑适用于下一条语句。

也就是说，这是一个非常愚蠢的面试问题，老实说，我不知道他们在做什么。就个人而言，我会质疑有人试图评估你编写这样的代码的能力是否明智。

希望这可以帮助！

Answer 2

tNode pHead;
tNode pTail;

void init() {
  pHead.pNext = &pTail;
  pTail.pNext = &pHead;
}

AddTail(tNode* pNode){
  pTail.pNext->pNext = pNode;
  pNode->pNext = &pHead;
  pTail.pNext = pNode;
}

Answer 3

typedef struct tNode_ tNode;

struct tNode_ {
  tNode* pNext;
  int data;
};

/* normal initialization for pHead */

tNode* pHead = NULL;

/* the trick is to point at where you want the next pointer to go
 * instead of saving a pointer to the node.
 */
tNode** ppTail = &pHead;

AddTail(tNode* pNode){
  pNode->pNext = NULL;
  /* update the next pointer */
  *ppTail = pNode;
  /* save the address of the next pointer */
  ppTail = &pNode->pNext;
}

main(){
  int cnt;

  tNode* pNew;

  for(cnt=0; cnt<10; cnt++){
    pNew = malloc(sizeof(tNode));
    pNew->data = cnt;
    AddTail(pNew);
  }

  for(pNew = pHead; pNew; pNew = pNew->pNext){
    printf("%d\n", pNew->data);
  }
}

Answer 4

我会为每个列表使用一个虚拟元素（或他们称之为哨兵节点）。附加到头部成为附加到虚拟对象，附加到尾部只是附加到最后一个元素，然后根据定义存在。

typedef struct tNode_ tNode;

struct tNode_ {
  tNode* pNext;
  int data;
};

// The Remove operation must never remove this dummy!
tNode* pDummy = (tNode*)calloc(1, sizeof(tNode));
tNode* pHead = pDummy;
tNode* pTail = pDummy;

AddTail(tNode* pNode){
  pTail->pNext = pNode;
  pTail = pNode;
  pTail->pNext = NULL;
}