链表操作(创建空链表、头插法、尾插法、反转链表、修改、删除链表元素、获取链表元素位置)

  1 #include<iostream>
  2 #include<string>
  3 #include<vector>
  4 #include<list>
  5 #include<stack>
  6 using namespace std;
  7 
  8 struct ListNode {
  9     int val;
 10     ListNode *next;
 11     ListNode(int x) : val(x), next(nullptr) {}
 12 };
 13 
 14 
 15 class Solution {
 16 public:
 17     void reverseNode(ListNode *&head) {
 18         ListNode *newNode = nullptr;
 19         while (head != nullptr) {
 20             ListNode *tmpNode = head->next;
 21             head->next = newNode;
 22             newNode = head;
 23             head = tmpNode;
 24         }
 25         head = newNode;
 26     }
 27 
 28     void insertNodeAtHead(ListNode *&head, int val) {
 29         ListNode *newNode = new ListNode(val);
 30         newNode->next = head;
 31         head = newNode;
 32     }
 33 
 34     void insertNodeAtTail(ListNode *&head , int val) {
 35         ListNode *newNode = new ListNode(val);
 36         newNode->next = nullptr;
 37         ListNode *cur = head;
 38         if (cur == nullptr) {
 39             head = newNode;
 40             return;
 41         }
 42         while (cur->next != nullptr) {
 43             cur = cur->next;
 44         }
 45         cur->next = newNode;
 46     }
 47 
 48     void printfListNode(ListNode *head) {
 49         while (head != nullptr)
 50         {
 51             printf("%d ", head->val);
 52             head = head->next;
 53         }
 54         printf("\n");
 55     }
 56 
 57     void modHeadVal(ListNode *&head, int val1, int val2) {
 58         ListNode *cur = head;
 59         while (cur->next != nullptr) {
 60             if (cur->next->val == val1) {
 61                 cur->next->val = val2;
 62             }
 63             cur = cur->next;
 64         }
 65     }
 66 
 67     void deleteNode(ListNode *&head, int val) {
 68         if (head == nullptr) {
 69             return;
 70         }
 71         ListNode *cur = head;
 72         while(cur->next != nullptr) {
 73             if (cur->next->val == val) {
 74                 cur->next = cur->next->next;
 75             } else {
 76                 cur = cur->next;
 77             }
 78         }
 79     }
 80     void getValIndexList(ListNode *head, int val, vector<int> &indexList) {
 81         ListNode *cur = head;
 82         int count = 0;
 83         while (cur->next != nullptr) {
 84             if (cur->val == val) {
 85                 indexList.push_back(count);
 86             }
 87             cur = cur->next;
 88             count++;
 89         }
 90         if (cur->val == val) {
 91             indexList.push_back(count);
 92         }
 93     }
 94 };
 95 
 96 
 97 int main()
 98 {
 99     Solution *s1 = new (Solution);
100     ListNode *head = nullptr;
101     vector<int> vec = {1, 2, 3, 4, 5, 6};
102     for (const auto &val : vec) {
103         s1->insertNodeAtHead(head, val);
104     }
105     s1->printfListNode(head); // 6 5 4 3 2 1
106     s1->insertNodeAtTail(head, 7);
107     s1->printfListNode(head); // 6 5 4 3 2 1 7
108 
109     s1->reverseNode(head);
110     s1->printfListNode(head); // 7 1 2 3 4 5 6
111     s1->deleteNode(head, 5);
112     s1->printfListNode(head); // 7 1 2 3 4 6
113     s1->modHeadVal(head, 3, 33);
114     s1->printfListNode(head); // 7 1 2 33 4 6
115     vector<int> vec1;
116     s1->getValIndexList(head, 4, vec1);
117     for (const auto &val : vec1) {
118         printf("%d ", val); // 4
119     }
120     printf("\n");
121     delete s1;
122     return 0;
123 }

 


上一篇:最长上升子序列 II


下一篇:【题解】ones 唯“一”运算