在链接列表C++中的某个位置插入节点

Question

我正在尝试在某个位置插入一个节点.在我的代码中,位置1的数字仅被插入(基本上在链表的开头)并且它没有插入位置2的任何数据.是否有一些错误的temp2？当我运行程序时,它并没有指向我想的任何东西.

我知道你们有多讨厌这里被问到的家庭作业问题,但我不知道我的课程有什么问题.我只是一个初学者,我的老师没有很好地解释链表.

代码如下.

- 我得到的输出是8 7

- 我希望它读取8 6 7 5,其中6和5插入位置2

/*
Insert node at a given positon in a linked list.
First element in the linked list is at position 0
*/

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

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

struct Node *head;

void Insert(int data, int n)
{
   Node* temp1 = new Node();
   temp1->data = data;
   temp1->next = NULL;
   if (n == 1){
    temp1->next = head;
    head = temp1;
    return;
   }
   Node* temp2 = new Node();
   for (int i = 0; i < n-2; i++){// i feel like it doesn't even go through this loop
    temp2 = temp2->next;
   }
   temp1->next = temp2->next;
   temp2->next = temp2;
}
void print()
{
    Node* temp = head;
    while(temp != NULL){
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
int main()
{
    head = NULL; //empty linked list
    Insert(7,1); //List: 7     
    Insert(5,2); //List: 7,5   
    Insert(8,1); //List: 8,7,5 
    Insert(6,2); //List: 8,6,7,5      
    print();
system("pause");
} 

Answer 1

只需要这样的东西,你遍历到给定的位置,然后插入:

void addNodeAtPos(int data, int pos)
{
  Node* prev = new Node();
  Node* curr = new Node();
  Node* newNode = new Node();
  newNode->data = data;

  int tempPos = 0;   // Traverses through the list

  curr = head;      // Initialize current to head;
  if(head != NULL)
  {
    while(curr->next != NULL && tempPos != pos)
    {
        prev = curr;
        curr = curr->next;
        tempPos++;
    }
    if(pos==0)
    {
       cout << "Adding at Head! " << endl;
       // Call function to addNode from head;
    }
    else if(curr->next == NULL && pos == tempPos+1)
    {
      cout << "Adding at Tail! " << endl;
      // Call function to addNode at tail;
    }
    else if(pos > tempPos+1)
      cout << " Position is out of bounds " << endl;
     //Position not valid

    else
    {
        prev->next = newNode;
        newNode->next = curr;
        cout << "Node added at position: " << pos << endl;
    }
 }
 else
 {
    head = newNode;
    newNode->next=NULL;
    cout << "Added at head as list is empty! " << endl;
 }
}

Answer 2

对于在特定位置插入k，您需要遍历列表直到该位置k-1，然后进行插入。

[您不需要像在代码中那样创建一个新节点来遍历到该位置]您应该从头节点开始遍历。