【数据结构初阶】链表OJ
链表OJ
- 题目一：移除链表元素
- 题目二：反转链表
- 题目三：链表的中间节点
- 题目四：链表中倒数第k个结点
- 题目五：合并两个有序链表
- 题目六：链表分割
- 题目七：链表的回文结构
- 题目八：相交链表
- 题目九：环形链表
- 题目十：环形链表II
题目一：移除链表元素
OJ
方案一：
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head, * prev = NULL;
while (cur)
{
if (cur->val == val)
{
if (cur == head)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
方案二：
题目解析：把原链表遍历一遍，插入新链表
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newnode = NULL, * tail = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->val == val)
{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}
else
{
if (tail == NULL)
{
newnode = tail = cur;
//tail = tail->next;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
}
if (tail)
tail->next = NULL;
return newnode;
}
题目二：反转链表
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newnode = NULL, * cur = head;
while (cur)
{
struct ListNode* next = cur->next;
//尾插
cur->next = newnode;
newnode = cur;
cur = next;
}
return newnode;
}
题目三：链表的中间节点
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
题目四：链表中倒数第k个结点
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* fast = pListHead, * slow = pListHead;
while (k--)
{
if (fast == NULL)
return NULL;
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
题目五：合并两个有序链表
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
return list2;
if (list2 = NULL)
return list1;
struct ListNode* tail = NULL, * head = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while (list1 && list2)
{
if (list1->val < list2->val)
{
tail->next = list1;
tail = tail->next;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = tail->next;
list2 = list2->next;
}
}
if (list1)
tail->next = list1;
if (list2)
tail->next = list2;
struct ListNode* del = head;
head = head->next;
free(del);
return head;
}
题目六：链表分割
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Partition
{
public:
ListNode* partition(ListNode* pHead, int x)
{
struct ListNode* lhead, * ltail, * gtail, * ghead;
ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while (cur)
{
if (cur->val < x)
{
ltail->next = cur;
ltail = ltail->next;
}
else
{
gtail->next = cur;
gtail = gtail->next;
}
cur = cur->next;
}
ltail->next = ghead->next;
gtail->next = NULL;
struct ListNode* head = lhead->next;
free(lhead);
free(ghead);
return head;
}
};
题目七：链表的回文结构
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList
{
public:
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newnode = NULL, * cur = head;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = newnode;
newnode = cur;
cur = next;
}
return newnode;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode* mid = middleNode(A);
struct ListNode* rmid = reverseList(mid);
while (A && rmid)
{
if (A->val != rmid->val)
return false;
A = A->next;
rmid = rmid->next;
}
return true;
}
};
题目八：相交链表
OJ
题目解析：
定义快慢指针，使快指针先走与慢指针同步。然后同时走看是否相交
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA, * curB = headB;
int lenA = 1, lenB = 1;
while (curA)
{
curA = curA->next;
lenA++;
}
while (curB)
{
curB = curB->next;
lenB++;
}
if (curA != curB)
return false;
int gab = abs(lenA - lenB);
struct ListNode* longest = headA, * shortest = headB;
if (lenA < lenB)
{
longest = headB;
shortest = headA;
}
while (gab--)
{
longest = longest->next;
}
while (shortest != longest)
{
shortest = shortest->next;
longest = longest->next;
}
return longest;
}
题目九：环形链表
OJ
题目解析：
代码演示：
struct ListNode {
int val;
struct ListNode* next;
};
bool hasCycle(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
题目十：环形链表II
OJ
题目解析：
代码演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode* meet = slow;
while(meet != head)
{
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}
💘不知不觉，【数据结构初阶】链表OJ以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!