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

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("%dn", pNew->data);
  }
}

Answer 3

我会为每个列表使用一个虚拟元素(或者他们所说的哨兵节点)。附加到头部变成附加到dummy，附加到尾部只是附加到最后一个元素，然后根据定义存在。

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;
}

Answer 4

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;
}