0

我被要求编写一个函数 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;
}
4

3 回答 3

1

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

1）首先创建一个列表。

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

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

于 2013-04-13T06:58:44.557 回答
0

这是一个大概的要点：

new_head_index = (ll->size+1) / 2;
new_tail_index = new_head_index - 1;

if (new_tail_index < 0)
    return;

new_head = findNode(ll,new_head_index);
new_tail = findNode(ll,new_tail_index);

ll->tail->next = ll->head;
new_tail->next = NULL
ll->head = new_head;
于 2013-04-13T05:41:45.500 回答
0

这是反转链表后半部分（右）的代码。

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

struct Node{
  int data;
  struct Node* next;
};

void append(struct Node** head_ref, int new_data)
{

  struct Node* new_node=(struct Node*)malloc(sizeof(struct Node));
  new_node->data=new_data;
  new_node->next=NULL;

  struct Node* last=*head_ref;
  if(*head_ref==NULL){
      *head_ref=new_node;
      return;
  }

while(last->next!=NULL)
    last=last->next;

last->next=new_node;
return;

}

int display(struct Node* n)
{
  int m=0;
  printf("\n");
  while(n!=NULL)
  {
      printf(" %d ",n->data);
      n=n->next;
      m=m+1;
  }

return m;
}

void reverse(struct Node** head_ref, int mid)
{
if(*head_ref==NULL)
{
    printf("\nEmpty List cannot be reversed");
    return;
}

struct Node* last=*head_ref;
struct Node* second_last;
struct Node* beg=*head_ref;
int c=1;
while(c<=mid){
    second_last=last;
    last=last->next;
    c=c+1;
}

struct Node* prev=NULL;
struct Node* current=last;
struct Node* next;

while(current != NULL)
{
    next=current->next;
    current->next=prev;
    prev=current;
    current=next;
}
*head_ref=beg;
second_last->next=prev;

}

int main()
{
int size;
struct Node* head=NULL;
int i,mid;
for(i=0;i<11;i++)
{
    append(&head,rand()%19 +1);
}
size=display(head);
printf("\n Size of linked list: %d",size);

if(size%2==0)
    mid=(size+1)/2;
else
    mid=size/2;

reverse(&head, mid);
display(head);
return 0;
}
于 2017-12-05T20:08:40.227 回答