Data Structures and Algorithms 1-1. List (2/2)
List
Leetcode- 141, 142, 202, 206, 92, 25, 61, 19, 83, 82, 86, 138
Problem solving tips
1. Determine the circle in a list: Fast & Slow pointer.
2. Head address may change: Create a virtual head node.
141
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr) return false;
ListNode *p, *q;
p = head;
q = head->next;
while (p && q && q->next) {
if (p == q) return true;
p = p->next;
q = q->next->next;
}
return false;
}
};
142
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr) return nullptr;
ListNode *p, *q;
p = q = head;
if (!q->next) return nullptr;
p = p->next;
q = q->next->next;
while (q && q->next) {
p = p->next;
q = q->next->next;
if (p == q) break;
}
if (!q|| !q->next) return nullptr;
q = head;
while (p != q) {
p = p->next;
q = q->next;
}
return p;
}
};
202
class Solution {
public:
int GetNext(int n) {
int cnt = 0;
while (n) {
int tmp = n % 10;
n /= 10;
cnt += tmp * tmp;
}
return cnt;
}
bool isHappy(int n) {
int fast, slow;
fast = slow = n;
do{
slow = GetNext(slow);
fast = GetNext(GetNext(fast));
if (slow == 1 || fast == 1) return true;
} while (fast != slow);
return false;
}
};
206 - solution 1
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head) return head;
ListNode *h, *t;
h = nullptr, t = head;
while (t) {
ListNode* tmp = t->next;
t->next = h;
h = t;
t = tmp;
}
return h;
}
};
206 - solution 2
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *h = head, *t = head->next, *p = reverseList(head->next);
h->next = t->next;
t->next = h;
return p;
}
};
92
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) return head;
ListNode *h = head, *t = head->next, *p = reverseN(head->next, n - 1);
h->next = t->next;
t->next = h;
return p;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head) return head;
int n = right - left;
ListNode ret(0, head);
ListNode *p = &ret;
while (left - 1) {
p = p->next;
left--;
}
p->next = reverseN(p->next, n + 1);
return ret.next;
}
};
25
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) return head;
ListNode *h = head, *t = head->next, *p = reverseN(head->next, n - 1);
h->next = t->next;
t->next = h;
return p;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head) return head;
int n = k;
ListNode ret(0, head);
ListNode *p = &ret, *h, *t;
h = t = p;
while (n && t && t->next) {
t = t->next;
n--;
if (n == 0) {
p = h->next;
h->next = reverseN(h->next, k);
h = t = p;
n = k;
}
}
return ret.next;
}
};
61
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return head;
ListNode *h, *t;
h = t = head;
int len = 0;
while (h) {
len++;
h = h->next;
}
h = head;
k = k % len;
while (k) {
t = t->next;
k--;
}
while (t->next) {
h = h->next;
t = t->next;
}
t->next = head;
t = h->next;
h->next = nullptr;
return t;
}
};
19
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode ret(0, head), *p1, *p2;
p1 = p2 = &ret;
while (n--) {
p1 = p1->next;
}
while (p1->next) {
p1 = p1->next;
p2 = p2->next;
}
p2->next = p2->next->next;
return ret.next;
}
};
83
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode *p = head;
while (p->next) {
if (p->val == p->next->val) {
p->next = p->next->next;
} else {
p = p->next;
}
}
return head;
}
};
82
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
ListNode ret(0, head);
ListNode *p, *q;
p = &ret;
while (p->next) {
if (p->next->next && p->next->val == p->next->next->val) {
q = p->next->next;
while (q && q->val == p->next->val) {
q = q->next;
}
p->next = q;
} else {
p = p->next;
}
}
return ret.next;
}
};
86
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode ret1(0), ret2(0);
ListNode* p1 = &ret1, *p2 = &ret2, *cur = head;
while (cur) {
if (cur->val < x) {
p1->next = cur;
p1 = p1->next;
} else {
p2->next = cur;
p2 = p2->next;
}
cur = cur->next;
}
p1->next = ret2.next;
p2->next = nullptr;
return ret1.next;
}
};
138
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return head;
Node *p = head, *q;
while (p) {
Node *q = new Node(p->val);
q->next = p->next;
p->next = q;
p = p->next->next;
}
p = head;
Node *tmp = head->next;
while (p) {
q = p->next;
if (!p->random) q->random = nullptr;
else q->random = p->random->next;
p = q->next;
}
p = head;
while (p) {
q = p->next;
p->next = p->next->next;
if (q->next) {
q->next = q->next->next;
}
p = p->next;
}
return tmp;
}
};
Yingzhe Dong
Graduate Student of Computer Science
I am a full-stack developer with interests in software development, system architecture, and distributed system.