CST204 Data Structures(CPP_ver)2

This time we learn List.

#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

class Node
{
public:
    double data;
    Node *next;
};

class List
{
private:
    Node *head;
public:
    List(void)
    {
        head = NULL;
    }// this is a construct function, to construct the "head" node
    ~List(void);// distrucrt
    bool IsEmpty()
    {
        return head == NULL;
    }
    Node *InsertNode(int index, double x);
    int FindNode(double x);
    int DeleteNode(double x);
    void DisplayList(void);
};

Node *List::InsertNode(int index, double x)
{
    if (index < 0) 
        return NULL;
    int currIndex = 1;
    Node *currNode = head;
    while (currNode && index > currIndex)
    {//currNode to test whether it reaches tail 
        currNode = currNode->next;
        currIndex++;
    }
    //after this while loop, it reaches the right position
    if (index > 0 && currNode == NULL)
    {
        return NULL;// index greater
    }
    Node *newNode = newNode;
    newNode->data = x;
    if (index == 0)
    {//
        newNode->next = head;
        head = newNode;
    }
    else
    {
        newNode->next = currNode->next;
        currNode->next = newNode;
    }
    return newNode;
};
int List::FindNode(double x)
{
    Node *currNode = head;
    int currIndex = 1;
    while (currNode && currNode->data != x)
    {
        currNode = currNode->next;
        currIndex++;
    }
    if (currNode)
        return currIndex - 1;
    return -1;
}
int List::DeleteNode(double x)
{
    Node *prevNode = NULL;
    Node *currNode = head;
    int currIndex = 1;
    while (currNode && currNode->data != x)
    {
        prevNode = currNode;
        currNode = currNode->next;
        currIndex++;
    }
    if (currNode)
    {
        if (prevNode)
        {
            prevNode->next = currNode->next;
            delete currNode;
        }
        else
        {
            head = currNode->next;
            delete currNode;
        }
        return currIndex;
    }
    return 0;
}
void List::DisplayList()
{
    int num = 0;
    Node *currNode = head;
    while (currNode != NULL)
    {
        cout << currNode->data << endl;
        currNode = currNode->next;
        num++;
    }
    cout << "Number of nodes in the list: " << num << endl;
}
List::~List(void)
{
    Node *currNode = head, *nextNode = NULL;
    while (currNode != NULL)
    {
        nextNode = currNode->next;
        // destroy the current node
        delete currNode;
        currNode = nextNode;
    }
}

int main(void)
{
}

But there is a bug in this code. If you ask it to insert a new node after the fifth element, but there are only three nodes in the list, it will crash.

So we can test the requirement before it tries to add one node. Just compare index and currIndex.

https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {

        ListNode* cur = head;
        ListNode* right = head;
        ListNode* left = nullptr;
        int cur_index = 0;
        while(cur){
            cur_index++;
            if(cur_index == k){
                left = cur;
            }
            if(cur_index > k){
                right = right->next;
            }
            cur = cur->next;
        }
        swap(right->val,left->val);
        return head;



    }
};

作者：CoKoi
链接：https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/solutions/2358830/guan-jian-shi-ru-he-zhao-dao-dao-shu-di-a2dj0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
大概思想很简单，搞两个指针指向头，其中一个指针不动，另一个指针指到第K个，存起来，然后两个指针一起动，先动的指针指到尾部，后动的指针就指到倒数第K个了。

Views: 113