https://github.com/gzc/CLRS/blob/master/C10-Elementary-Data-Structures/10.2.md
Exercises 10.2-1
Can you implement the dynamic-set operation INSERT on a singly linked list in O(1) time? How about DELETE?
You can implement INSERT in constant time by prepending it to the list.
You cannot implement DELETE in constant time, unless you pass to it as an argument the predecessor of the element you are deleting.
Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? How about DELETE?
插入的话可以直接插入在开头,删除的话需要遍历.
http://blog.csdn.net/lihenair/article/details/18046437
insert(LinkList *tail, ElemType x)
{
Node* p = new Node;
p->value = x;
p->next = tail;
tail = p;
}
delete(LinkList *tail)
{
Node* p = tail;
tail = p-> next;
delete p;
}
Exercises 10.2-2
Implement a stack using a singly linked list L. The operations PUSH and POP should still take O(1) time.
PUSH插入到链表头,POP从链表头操作,都是O(1)的.
Exercises 10.2-3
Implement a queue by a singly linked listL. The operations ENQUEUE and DEQUEUE should still take O(1)time.
an->an-1->......->a2->a1->nil
↑ ↑
head tail
在头部Dequeue,在尾部Enqueue。
Exercises 10.2-7
Give a Θ(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.
https://github.com/KickAlgorithm/leetcode/blob/master/cpp/201-210/Reverse%20Linked%20List.cpp
ListNode* reverseList(ListNode* head) {
ListNode *tmp(NULL),*prev(NULL);
while(head)
{
tmp = head->next;
head->next = prev;
prev = head;
head = tmp;
}
return prev;
}
Exercises 10.2-1
Can you implement the dynamic-set operation INSERT on a singly linked list in O(1) time? How about DELETE?
You can implement INSERT in constant time by prepending it to the list.
You cannot implement DELETE in constant time, unless you pass to it as an argument the predecessor of the element you are deleting.
Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? How about DELETE?
插入的话可以直接插入在开头,删除的话需要遍历.
http://blog.csdn.net/lihenair/article/details/18046437
insert(LinkList *tail, ElemType x)
{
Node* p = new Node;
p->value = x;
p->next = tail;
tail = p;
}
delete(LinkList *tail)
{
Node* p = tail;
tail = p-> next;
delete p;
}
Exercises 10.2-2
Implement a stack using a singly linked list L. The operations PUSH and POP should still take O(1) time.
PUSH插入到链表头,POP从链表头操作,都是O(1)的.
Exercises 10.2-3
Implement a queue by a singly linked listL. The operations ENQUEUE and DEQUEUE should still take O(1)time.
an->an-1->......->a2->a1->nil
↑ ↑
head tail
在头部Dequeue,在尾部Enqueue。
Exercises 10.2-7
Give a Θ(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.
https://github.com/KickAlgorithm/leetcode/blob/master/cpp/201-210/Reverse%20Linked%20List.cpp
ListNode* reverseList(ListNode* head) {
ListNode *tmp(NULL),*prev(NULL);
while(head)
{
tmp = head->next;
head->next = prev;
prev = head;
head = tmp;
}
return prev;
}