Toughest Solution Known to mankind with Linked List
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Node{\n    public:\n    int val;\n    Node* next;\n    Node(){}\n    Node(int val){\n        this->val = val;\n        next = nullptr;\n    }\n};\n\nvoid insertHead(Node *&head,Node *&tail,int val){\n      Node * newnode=new Node(val);\n      if(head==nullptr){\n          head=newnode;\n          tail=newnode;\n      }\n      else{\n          newnode->next=head;\n          head=newnode;\n      }\n    }\n\nvoid insertTail(Node *&head,Node *&tail ,int val){\n     Node * newnode=new Node(val);\n      if(tail==nullptr){\n          tail=newnode;\n          head=newnode;\n      }\n      else{\n          tail->next=newnode;\n          tail=newnode;\n      } \n}\n\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        Node *head = nullptr;\n        Node *tail = nullptr;\n        int maxi = INT_MIN;\n\n        for (auto i : arr) {\n            maxi = max(maxi, i);\n            insertTail(head, tail, i);\n        }\n\n        Node *temp1 = head;\n        Node*temp2 = head->next;\n        pair<int, int> counter = {0, 0};\n\n        while (counter.second != k && counter.first != maxi) {\n            if (temp1->val == maxi || temp2->val == maxi) return maxi;\n            \n            Node *temp1 = head;\n            Node*temp2 = head->next;       \n            int winner;\n\n            if (temp1->val > temp2->val) {\n                winner = temp1->val;\n                temp1->next = temp2->next;\n                temp2->next = nullptr;\n                insertTail(head, tail, temp2->val);\n            } else {\n                winner = temp2->val;\n                head= temp2;\n                temp1->next = nullptr;\n                insertTail(head, tail, temp1->val);\n            }\n\n            if (counter.first == winner) {\n                counter.second++;\n            } else {\n                counter = {winner, 1};\n            }\n        }\n\n        if (counter.first == maxi) {\n            return maxi;\n        }\n        return counter.first;\n    }\n};\n\n```
['C++']