Skip to main content Link Menu Expand (external link) Document Search Copy Copied

CS162 - 3A

TABLE OF CONTENTS

Problem statements

  1. Insert a new Node to ther beginning of the list
    void insertAtBeginning(Node* pHead, int x);
  2. Insert a new Node x after the \(1^{st}\) Node k (By saying Node x, it means the Node with the value of x).
    Notes: if there is no k, don’t insert.
    void insertAfterK(Node* pHead, int x, int k);

Student’s code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <iostream>

using namespace std;

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

void inputLL(Node*& pHead);
void displayLL(Node* cur);
void deleteLL(Node*& pHead);
void insertAtBeginning(Node*& pHead, int x);
void insertAfterK(Node* pHead, int x, int k);

int main(){
    Node* pHead = nullptr;
    
    inputLL(pHead);
    int x;
    cout << "data: ";
    cin >> x;
    insertAtBeginning(pHead, x);
    displayLL(pHead);
    
    cout << "data: ";
    cin >> x;
    cout << "value to insert after: ";
    int k;
    cin >> k;
    insertAfterK(pHead, x, k);
    displayLL(pHead);
    
    deleteLL(pHead);
    displayLL(pHead);
}

void inputLL(Node*& pHead) {    
    int x;
    cout << "Please input the number: ";
    cin>>x;
    Node* cur = nullptr;
    while(x != 0)
    {
        if(pHead == nullptr) {
            pHead = new Node;
            cur = pHead;
        }
        else {
            cur->pNext = new Node;
            cur = cur->pNext;
        }
        
        cout << "Please input the number: ";
        cin>>x;
        cur->data = x;
        cur->pNext = nullptr;
    }
}

void displayLL(Node* cur) {
    for (; cur != nullptr; cur = cur->pNext)
    {
        cout << cur->data << endl;
    }
}

void deleteLL(Node*& pHead) {
    while(pHead != nullptr)
    {
        Node* next = pHead->pNext;
        delete pHead;
        pHead = next;
    }
}

void insertAtBeginning(Node*& pHead, int x) {
    Node* newNode = new Node;
    newNode->data = x;
    newNode->pNext = pHead;
    pHead = newNode;
}

void insertAfterK(Node* pHead, int x, int k) {
    while(pHead != nullptr && pHead->data != k) {
        pHead = pHead->pNext;
    }
    if(pHead == nullptr) {
        return;
    }
    Node* newNode = new Node;
    newNode->data = x;
    newNode->pNext = pHead->pNext;
    pHead->pNext = newNode;
}

Teacher’s Notes

  • The order of line 80 and line 81 is very important.
  • If you run pHead in the function void insertAfterK() which if passed by value, it will not change the value of the actual pHead. Thus it’s safe to be iterating through the linked list.
  • The if statement at line 88 means there’re no Node k in the linked list.

Visualization

1

void insertAtBeginning(Node*& pHead, int x);


1

void insertAfterK(Node* pHead, int x, int k);

Additional sub-problem:

  1. Insert Node x before Node k.
    void insertBeforeK(Node*& pHead, int x, int k);

Student’s code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void insertBeforeK(Node*& pHead, int x, int k) {
    Node* cur = pHead;
    while(cur != nullptr && cur->pNext->data != k) {
        cur = cur->pNext;
    }
    
    if(cur == nullptr) {
        return;
    }
    
    Node* newNode = new Node;
    newNode->data = x;
    newNode->pNext = cur->pNext;
    cur->pNext = newNode;
    
    if(cur == pHead) {
        insertAtBeginning(pHead, x);
    }
}

Teacher’s code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void insertBeforeK(Node*& pHead, int x, int k) {
    Node* cur = pHead;
    
    if(!cur) return;
    if(cur->data == k) {
        insertAtBeginning(pHead, x);
        return;
    }

    while(cur && cur->pNext && cur->pNext->data != k) {
        cur = cur->pNext;
    }
    
    if(!cur->pNext) return;
    
    Node* newNode = new Node;
    newNode->data = x;
    newNode->pNext = cur->pNext;
    cur->pNext = newNode;
}

Notes:

  • Make sure that everytime you use a pointer, you have to make sure that the pointer is valid (not a nullptr)