Challenge 4 dan 5 dari tugas Struktur Data

challenge4.cpp

#include <iostream>
struct Node {
  int data;
  Node* next;

  Node(int d) {
    this->data = d;
    this->next = nullptr;
  }
};


class LinkedList {
public:
  LinkedList() {
    this->_head = nullptr;
  }

  Node* _head;
  Node* _tail;

  /**
   * returns the new head
   * */
  Node* push(Node* new_node);
};

Node* LinkedList::push(Node* new_node) {
  if(this->_head == nullptr) {
    this->_head = new_node;
    this->_tail = new_node;
    return this->_head;
  }

  this->_tail->next = new_node;
  this->_tail = new_node;
  return this->_head;
}

Node* find_kth(LinkedList* l, int k) {
  if(l->_head == nullptr) return nullptr;
  Node* current = l->_head;

  if(current->next == nullptr) {
    return current;
  }

  Node* tip = current; 
  for (int i = 0; i < k-1; i++) {
    tip = tip->next; 
  }

  while(tip->next != nullptr) {
    tip = tip->next;
    current = current->next;
  }
  
  return current;
}

int main() {
  Node head_node(10);
  Node b(20);
  Node c(30);
  Node d(40);
  Node e(50);
  Node f(60);

  LinkedList l1;
  l1.push(&head_node);
  l1.push(&b);
  l1.push(&c);
  l1.push(&d);
  l1.push(&e);
  l1.push(&f);

  Node* kth = find_kth(&l1, 3);
  std::cout << kth->data << '\n';
  
  return 0;
}

challenge5.cpp

#include <iostream>

struct Node {
  int data;
  Node* next;

  Node(int d) {
    this->data = d;
    this->next = nullptr;
  }
};


class LinkedList {
public:
  LinkedList() {
    this->_head = nullptr;
  }

  Node* _head;
  Node* _tail;

  /**
   * returns the new head
   * */
  Node* push(Node* new_node);
};

Node* LinkedList::push(Node* new_node) {
  if(this->_head == nullptr) {
    this->_head = new_node;
    this->_tail = new_node;
    return this->_head;
  }

  this->_tail->next = new_node;
  this->_tail = new_node;
  return this->_head;
}

void print_nodes(LinkedList* l) {
  Node* current = l->_head;

  while(current != nullptr) {
    std::cout << current->data;
    if(current->next != nullptr) {
      std::cout << " -> ";
      current = current->next;
    } else {
      break;
    }
  }
}

/**
 * merges two linked lists into the first LinkedList
 * returns a pointer to the first LinkedList in the param list 
 * */
LinkedList* merge_lists(LinkedList* l1, LinkedList* l2) {
  Node* min = l1->_head;
  if(min->next == nullptr) {
    // TODO
    return l1;
  }

  Node* max = min->next;
  Node* p = l2->_head;

  while (l2->_head != nullptr && p->next != nullptr) {
    Node* p = l2->_head;
    l2->_head = p->next;

    if(p->data <= min->data) {
      p->next = min;
      p = l2->_head; // moving p up l2.
    } else if(min->data < p->data &&  p->data < max->data) {
      min->next = p;
      p->next = max;
      min = p;
    } else if (max->data < p->data) {
      Node* maxnext = max->next; // temp var so l1 doesn't dangle
      max->next = p;
      p->next = maxnext;
      min = max;
      max = p;
    }
  }

  while (max->next != nullptr) {
    Node* maxnext = max->next;

    if(max->data > maxnext->data) {
      int temp = max->data;
      max->data = maxnext->data;
      maxnext->data = temp;
    }

    min=max;
    max=maxnext;
  }



  return l1;
}

int main() {
  LinkedList l1;

  Node f_node(10);
  Node s_node(50);
  Node t_node(70);

  l1.push(&f_node);
  l1.push(&s_node);
  l1.push(&t_node);

  LinkedList l2;

  Node ff_node(20);
  Node ss_node(40);
  Node tt_node(60);

  l2.push(&ff_node);
  l2.push(&ss_node);
  l2.push(&tt_node);

  auto merged = merge_lists(&l1, &l2);

  print_nodes(merged);
}