Make writing a habit together! This is the 13th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

I plan to update the realization of all the code exercises of 23 Kingway data structure after class. Although the exam is generally written in pseudo-code, I still realized all of them because of obsessive-compulsive. The warehouse is here

  • The linear table 14/14
  • The list of 5/25

2.3.7, 3

  • Classical recursion, the exit is still null
  • The recursive stack is used to output node values in reverse
  • Time complexity O(n), space complexity O(n)
void reversePrintList(LinkList L) {
  if (L == NULL) return;
  reversePrintList(L->next);
  cout << L->data << "";
}
Copy the code
  • Run through the list from beginning to end, using a stack to store the value of each node and then output
  • Time complexity O(n), space complexity O(n)
void reversePrintList2(LinkList L) {
  if (L == NULL) return;
	
  // 1. Iterate over the storage
  stack<int> stack;
  while(L ! =NULL) {
    stack.push(L->data);
    L = L->next;
  }
  
  / / 2. The output
  while(! stack.empty()) {
    cout << stack.top() < <"";
    stack.pop();
  }
}
Copy the code

2.3.7, 4

  • With the order table to find the minimum value is basically the same, but need to add a pointer to the prefix for easy deletion
  • Define two Pointers: p and the prefix pre, and define minp and minpre to point to the current minimum node
  • Time complexity O(n), space complexity O(1)
void delMin(LinkList &L) {
  // 1. Define Pointers
  LNode *pre = L, *p = pre->next;
  LNode *minpre = pre, *minp = p;

  // 2. Find the minimum
  while(p ! =NULL) {
    if (p->data < minp->data) {
      minpre = pre;
      minp = p;
    }
    pre = p;
    p = p->next;
  }

  // 3. Delete the minimum
  minpre->next = minp->next;
  free(minp);
}
Copy the code

2.3.7, 5

  • Invert in place, which for a linked list of leading nodes is the node after the head node is inserted in the same way as the head node
  • Double pointer again, this time I need p and the suffix of p.
  • Headplugging means inserting a new P after an L every time! So L is still the head node, you don’t need to return a new list
  • Time complexity O(n), space complexity O(1)
void reverse(LinkList &L) {
  LNode *p = L->next, *q;
  L->next = NULL;

  while(p ! =NULL) {
    q = p->next;  // Record the suffix

    p->next = L->next;  // insert after L
    L->next = p;

    p = q;  // Continue to insert the next node}}Copy the code