C语言 (数据结构:链表)将奇数项移到链表的后面

Question

我应该实现一个函数void moveOddItemsToBack(LinkedList *ll)，将所有奇数移动到链表ll的后面。

它能够编译和运行，但是数字不是在正确的顺序，我不确定为什么:(我写的代码如下所示:

void moveOddItemsToBack(LinkedList *ll)
{
ListNode *cur = ll-> head;
int orgsize = ll->size; 
index =0;   
//check for empty list
if (cur == NULL) return;
//if list not empty, traverse entire list
while (orgsize > 0){
//if odd no
if (cur->item %2 !=0){
insertNode(ll, ll->size, cur->item);  //insert the odd number into last item on list
cur = cur -> next;
removeNode(ll, index); //remove the odd number in the original index
}
//if not odd no, just continue traversing list
else cur = cur -> next;
orgsize--;   //original size decreases every while loop so as to inspect the original nodes' integers and not the integers i added to the back of list
index++;  //index increases by 1 everytime i move my cur ptr to the next node
}
}

给出的主代码:

#include <stdlib.h>
//////////////////////////////////////////////////////////////////////////////////
typedef struct _listnode
{
int item;
struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode
typedef struct _linkedlist
{
int size;
ListNode *head;
} LinkedList;           // You should not change the definition of LinkedList

//////////////////////// function prototypes /////////////////////////////////////
// You should not change the prototype of this function
void moveOddItemsToBack(LinkedList *ll);
void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
//////////////////////////// main() //////////////////////////////////////////////
int main()
{
LinkedList ll;
int c, i, j;
c = 1;
//Initialize the linked list 1 as an empty linked list
ll.head = NULL;
ll.size = 0;

printf("1: Insert an integer to the linked list:n");
printf("2: Move all odd integers to the back of the linked list:n");
printf("0: Quit:n");
while (c != 0)
{
printf("Please input your choice(1/2/0): ");
scanf("%d", &c);
switch (c)
{
case 1:
printf("Input an integer that you want to add to the linked list: ");
scanf("%d", &i);
j = insertNode(&ll, ll.size, i);
printf("The resulting linked list is: ");
printList(&ll);
break;
case 2:
moveOddItemsToBack(&ll); // You need to code this function
printf("The resulting linked list after moving odd integers to the back of the linked list is: ");
printList(&ll);
removeAllItems(&ll);
break;
case 0:
removeAllItems(&ll);
break;
default:
printf("Choice unknown;n");
break;
}
}
return 0;
}

函数removeNode给定:

ListNode *pre, *cur;
// Highest index we can remove is size-1
if (ll == NULL || index < 0 || index >= ll->size)
return -1;
// If removing first node, need to update head pointer
if (index == 0){
cur = ll->head->next;
free(ll->head);
ll->head = cur;
ll->size--;
return 0;
}
// Find the nodes before and after the target position
// Free the target node and reconnect the links
if ((pre = findNode(ll, index - 1)) != NULL){
if (pre->next == NULL)
return -1;
cur = pre->next;
pre->next = cur->next;
free(cur);
ll->size--;
return 0;
}
return -1;
}

函数insertNode给定:

int insertNode(LinkedList *ll, int index, int value){
ListNode *pre, *cur;
if (ll == NULL || index < 0 || index > ll->size)
return -1;
// If empty list or inserting first node, need to update head pointer
if (ll->head == NULL || index == 0){
cur = ll->head;
ll->head = malloc(sizeof(ListNode));
ll->head->item = value;
ll->head->next = cur;
ll->size++;
return 0;
}

// Find the nodes before and at the target position
// Create a new node and reconnect the links
if ((pre = findNode(ll, index - 1)) != NULL){
cur = pre->next;
pre->next = malloc(sizeof(ListNode));
pre->next->item = value;
pre->next->next = cur;
ll->size++;
return 0;
}
return -1;
}

Answer 1

不需要计数;只对链表执行一次遍历:

---

#include <stdio.h>
typedef struct zzz {
struct zzz *next;
int item;
} LinkedList;
LinkedList items[] =
{ { items+1, 0 }
, { items+2, 1 }
, { items+3, 2 }
, { items+4, 3 }
, { items+5, 4 }
, { NULL, 5 }
};
void moveOddItemsToBack(LinkedList **ll);
void moveOddItemsToBack(LinkedList **ll)
{
LinkedList *odds=NULL, **pp = &odds;
for ( ; *ll;    ) {
LinkedList *this;
this = *ll;
/* leave this one; it is even */
if ( !( this->item %2) ) {
ll = &this->next;
continue;
}
/* Skip over it (cut it out of the original list)
** , and append to the list of odds
*/
*ll = this->next;
*pp = this;
pp = &this->next;
}
/* terminate odds-chain, and append to the tail of evens */
*pp = NULL;
*ll = odds;
}
int main(void)
{
LinkedList *root;
root = items;
moveOddItemsToBack(&root);
for (   ; root; root = root->next) {
printf("%dn", root->item);
}
return 0;
}