c - 反转列表的一半

Question

我被要求编写一个函数reverseHalves()，它重新排列给定的链表，以便将前半个节点移动到后半个节点的后面。例如

给定一个链接列表[1 2 3 4 5 6]，结果列表应为[4 5 6 1 2 3]。
当给定一个具有奇数个节点的链表时，该列表应该被分割，前半部分有一个额外的节点。也就是说，给定列表 [1 2 3 4 5]，结果列表应为 [4 5 1 2 3]。

但是我的函数将给出无限的输出......

typedef struct _listnode{
    int item;
    struct _listnode *next;
} ListNode;

typedef struct _linkedlist{
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

以下是我使用的函数:

// printList will print out the value in every nodes until there is a NULL
void printList(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);

void reverseHalves(LinkedList *ll)
{
    int index;
    ListNode *new_head, *new_tail;
    new_head = NULL;
    new_tail = NULL;

    // determine the index of new tail, and the new head which is index+1*
    index = (ll->size + 1) / 2;

    // get the new head by findNode func,whose index is index+1 
    // make new_head point to the node found*
    new_head = findNode(ll, index);

    // make initial tail->next be the initial head*
    ll->tail->next = ll->head;

    // set the head to be the new head
    ll->head = new_head;

    insertNode(ll, ll->size, -1);
    new_tail = findNode(ll, ll->size);
    new_tail = NULL;
}

Answer 1

我建议您分步骤编写问题代码。

1)首先创建一个列表。

2)拆分列表，得到两个列表。

3)将第二个列表的尾部添加到第一个列表的头部。