[算法专题] LinkedList – Acjx

前段时间在看一本01年出的旧书《effective Tcp/Ip programming》,这个算法专题中断了几天,现在继续写下去。

Introduction

对于单向链表(singly linked list),每个节点有⼀个next指针指向后一个节点,还有一个成员变量用以储存数值;对于双向链表(Doubly LinkedList),还有一个prev指针指向前一个节点。与数组类似,搜索链表需要O(n)的时间复杂度,但是链表不能通过常数时间读取第k个数据。链表的优势在于能够以较⾼的效率在任意位置插⼊或删除一个节点。

Dummy Node,Scenario: When the head is not determinated

之前在博客中有几篇文章,已经介绍了Dummy Node的使用,实际上Dummy Node就是所谓的头结点,使用Dummy Node可以简化操作,统一处理head与其他node的操作。

链表操作时利⽤用dummy node是⼀一个⾮非常好⽤用的trick:只要涉及操作head节点,不妨创建dummy node:

ListNode *dummy = new ListNode(0);
dummy->next = head;

废话少说,来看以下几道题:

1. Remove Duplicates from Sorted List I, II
2. Merge Two Sorted Lists
3. Partition List
4. Reverse Linked List I,II

1. Remove Duplicates from Sorted List I

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

这题我们的策略遇到重复的node,保留第一个,删除后面的,因此并不会改动head节点,所以下面的代码没有设置dummy node。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) {
return head;
}

ListNode *headBak = head;
while (head->next) {
if (head->val == head->next->val) {
// 保留第一个,删除后面的
ListNode *tmp = head->next;
head->next = tmp->next;
delete tmp;
} else {
head = head->next;
}
}

return headBak;
}
};

2. Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) {
return head;
}

ListNode *dummy = new ListNode(0);
dummy->next = head;

ListNode *pos = dummy;

// 至少需要head 和 head->next 才可能有重复
while (pos->next && pos->next->next) {
if (pos->next->val == pos->next->next->val) {
int preVal = pos->next->val;
// 至少保证有两个node,才会有重复
while (pos->next && pos->next->val == preVal) {
ListNode *tmp = pos->next;
pos->next = tmp->next;
delete tmp;
}
} else {
pos = pos->next;
}
}

return dummy->next;
}
};

3. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *curr = dummy;

while (l1 && l2) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}

curr = curr->next;
}

if (l1) {
curr->next = l1;
}

if (l2) {
curr->next = l2;
}

return dummy->next;
}
};

4. Partition List

https://leetcode.com/problems/partition-list/

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (head == NULL) {
return NULL;
}

ListNode *leftDummy = new ListNode(0);
ListNode *left = leftDummy;

ListNode *rightDummy = new ListNode(0);
ListNode *right = rightDummy;

ListNode *curr = head;

while (curr) {
if (curr->val < x) {
left->next = curr;
left = left->next;
curr = curr->next;
} else {
right->next = curr;
right = right->next;
curr = curr->next;
}
}

left->next = rightDummy->next;
right->next = NULL;

return leftDummy->next;
}
};

Basic Skills

5. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

非递归写法如下:

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) {
return NULL;
}

ListNode *pre = NULL;
ListNode *curr = head;
ListNode *next = NULL;
while (curr) {
next = curr->next;

curr->next = pre;
pre = curr;

curr = next;
}

return pre;
}
};

递归写法如下:

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseList(ListNode *head) {
// empty list
if (head == NULL) return head;
// Base case
if (head->next == NULL) return head;

// reverse from the rest after head
ListNode *newHead = reverseList(head->next);
// reverse between head and head->next
head->next->next = head;
// unlink list from the rest
head->next = NULL;

return newHead;
}
};

6. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL) {
return NULL;
}

ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *pos = dummy;

for (int i = 0; i <= m – 2; i++) {
pos = pos->next;
}
ListNode *mPreNode = pos;
ListNode *mCurrNode = pos->next;

ListNode *nPreNode = NULL;
ListNode *nCurrNode = mCurrNode;
ListNode *nNextNode = NULL;
for (int i = m; i <= n; i++) {
nNextNode = nCurrNode->next;

nCurrNode->next = nPreNode;
nPreNode = nCurrNode;

nCurrNode = nNextNode;
}

mPreNode->next = nPreNode;
mCurrNode->next = nCurrNode;

return dummy->next;
}
};

7. Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummy = new ListNode(0);
dummy->next = head;

ListNode *pre = dummy;
ListNode *curr = head;
while (curr) {
if (curr->val == val) {
ListNode *waitForDel = curr;

pre->next = curr->next;
curr = curr->next;

delete waitForDel;
} else {
pre = pre->next;
curr = curr->next;
}
}

return dummy->next;
}
};

8. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummy = new ListNode(0);
dummy->next = head;

ListNode *slow = dummy;
ListNode *fast = dummy;
for (int i = 0; i < n – 1; i++) {
fast = fast->next;
}

ListNode *pre = NULL;
while (fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next;
}

pre->next = slow->next;
delete slow;

return dummy->next;
}
};

9. Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *pos = head;
while (pos) {
if (pos->next && pos->val == pos->next->val) {
ListNode *waitForDel = pos->next;
pos->next = pos->next->next;
delete waitForDel;
} else {
pos = pos->next;
}
}

return head;
}
};

/**
*
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (head == NULL) {
return NULL;
}

ListNode *node = head;
while (node->next != NULL) {
if (node->val == node->next->val) {
ListNode *temp = node->next;
node->next = node->next->next;
delete temp;
} else {
node = node->next;
}
}

return head;
}
};
*
*/

10. Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) {
return head;
}

ListNode *dummy = new ListNode(0);
dummy->next = head;

ListNode *pos = dummy;

// 至少需要head 和 head->next 才可能有重复
while (pos->next && pos->next->next) {
if (pos->next->val == pos->next->next->val) {
int preVal = pos->next->val;
// 至少保证有两个node,才会有重复
while (pos->next && pos->next->val == preVal) {
ListNode *tmp = pos->next;
pos->next = tmp->next;
delete tmp;
}
} else {
pos = pos->next;
}
}

return dummy->next;
}
};

(待续)

8

8

8

本文链接:[算法专题] LinkedList,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量