如何在另一个链表中获取链表的奇数索引节点？我不想使用双指针

Question

我不想在我的代码中使用双指针，请假设第一个节点的索引为 1。我有一个链表 10->20->30->40->50->60-> 70->80->90->100->NULL 在另一个头指针为 pLink 的链表中，我想复制奇数索引节点并得到输出 10->30->50->70->90 ->NULL.

    SLLI*OddNodes(SLLI*pHead)
{
    int counter =1;
    SLLI*pTemp=pHead;
    SLLI*pList=NULL;
    while(pTemp != NULL)
    {
        if(counter % 2 != 0)
        {
           if(pList==NULL)
           {
               pList=malloc(sizeof(SLLI));
               pList->data=pTemp->data;
               pList->next=NULL;
           }
           else
           {
               SLLI*pIter=pList;
               SLLI*pNew=malloc(sizeof(SLLI));
               pNew->data=pTemp->data;
               pNew->next=NULL;
               pIter->next=pNew;
               pIter=pIter->next;

           }
        }
        pTemp=pTemp->next;
        counter ++;
    }
    return pList;
}

当我运行这段代码时，我得到输出 10->90->NULL 我知道 "else" 部分有问题。 SLLI*pIter=pList 没有任何意义，但我该怎么做才能消除这个错误？

Answer 1

我想问题是 pList 在你的 else 语句中根本没有改变。

这样行不行:

SLLI*OddNodes(SLLI*pHead)
{
   int counter =1;
   SLLI*pTemp=pHead;
   SLLI*pList=NULL;
   SLLI*pNewHead=NULL;

   while(pTemp != NULL)
   {
      if(counter % 2 != 0)
      {
         if(pList==NULL)
         {
            pList=malloc(sizeof(SLLI));
            pList->data=pTemp->data;
            pList->next=NULL;
            pNewHead = pList;
         }
         else
         {
            pList->next = malloc(sizeof(SLLI));
            pList->next->data = pTemp->data;
            pList->next->next = NULL;
            pList = pList->next;
         } 
         pTemp = pTemp->next;
         counter++
      }
   }

   return pNewHead;
}

另外我会检查malloc是否成功

Answer 2

给你。

#include <stdio.h>
#include <stdlib.h>

typedef struct SinglyLinkedListItem
{
    int data;
    struct SinglyLinkedListItem *next;
} SLLI;

SLLI * OddNodes( SLLI *pHead )
{
    int odd = 0;
    SLLI *pList = NULL;


    for ( SLLI *pCurrent = pList; pHead != NULL; pHead = pHead->next )
    {
        if ( odd ^= 1 )
        {
            if ( pCurrent == NULL )
            {
                pList = malloc( sizeof( SLLI ) );
                pList->data = pHead->data;
                pList->next = NULL;
                pCurrent = pList;
            }
            else
            {
                pCurrent->next = malloc( sizeof( SLLI ) );
                pCurrent->next->data = pHead->data;
                pCurrent->next->next = NULL;
                pCurrent = pCurrent->next;
            }
        }
    }

    return pList;
}
 int insert( SLLI **pHead, int data )
 {
    SLLI *pCurrent = malloc( sizeof( SLLI ) );
    int success = pCurrent != NULL;

    if ( success )
    {
        pCurrent->data = data;
        pCurrent->next = *pHead;
        *pHead = pCurrent;
    }

    return success;
 }

 void out( SLLI *pHead )
 {
    for ( ; pHead != NULL; pHead = pHead->next )
    {
        printf( "%d -> ", pHead->data );
    }

    puts( "null" );
 }

int main(void) 
{
    const int N = 10;

    SLLI *pHead = NULL;

    for ( int i = N; i != 0; --i )
    {
        insert( &pHead, 10 * i );
    }

    out( pHead );

    SLLI *pSecondHead = OddNodes( pHead );

    out( pHead );
    out( pSecondHead );

    return 0;
}

程序输出为

10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> 90 -> 100 -> null
10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> 90 -> 100 -> null
10 -> 30 -> 50 -> 70 -> 90 -> null

Answer 3

只是的 DRY 补充：

/**
 * Returns a list with the data from every other item starting at *original.
 * Does not modify the nodes from *original: malloc()s new nodes
 */
SLLI *OddNodes(SLLI const *original)
{
    int odd = 0;
    SLLI oddHead = { 0, NULL },
        *copy = &oddHead;

    for ( ; original != NULL ; original = original->next)
        if (odd ^= 1) {
            if (NULL == (copy->next = malloc(sizeof *copy)))
            /* alternatively, free "oddHead.next" & return NULL.
             * Should be documented in head comment! */
                exit(EXIT_FAILURE);
            copy = copy->next;
            copy->data = original->data;
            copy->next = NULL;
        }

    return oddHead.next;
}

如何在另一个链表中获取链表的奇数索引节点？我不想使用双指针

How can I get the odd indexed nodes of a linked list in an another linked list?I do not want to use double pointer

c

algorithm

data-structures

singly-linked-list