2.1 Write code to remove duplicates from an unsorted linked list
/* Link list node */
struct node
{
int data;
struct node* next;
};
void rem_duplicate(node *head){
if(NULL == head) return ;
set<int> hash;
set.insert(head->data);
while(head->next){
if(hash.find(head->next->data) == hash.end()){
node *tp = head->next;
head->next = tp->next;
delete tp;
}else{
hash.insert(head->next->data);
head = head ->next;
}
}
}
2.2 Implement an algorithm to fnd the nth to last element of a singly linked list
/* Link list node */
struct node
{
int data;
struct node* next;
};
node *nthToLast(node * head, int n){ if(NULL == head || n <) return NULL;
node *p;
p = head
for(int i = ; i < n; i++){
if(p== NULL) return NULL;
p = p->next;
}
node * q = head;
while(p->next){
p = p->next;
q = q->next;
}
return p;
}
2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node
/*
Initialize mid element as head and initialize a counter as 0. Traverse the list from head, while traversing increment the counter and change mid to mid->next whenever the counter is odd. So the mid will move only half of the total length of the list.
*/
/* Link list node */
struct node
{
int data;
struct node* next;
};
void deleteMiddle(struct node *head){
if(head == NULL) return ;
node * mid = head;
int count = 0;
while(head != NULL){
if(count & 1){
mid = mid->next;
}
count++;
head = head ->next;
} if(mid->next !=NULL)
{
mid->data = mid->next->data;
node *tp = mid->next;
mid->next = tp->next;
delete tp;
}else{
delete mid;
} }
reference :http://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/
2.4 You have two numbers represented by a linked list, where each node contains a single digit The digits are stored in reverse order, such that the 1’s digit is at the head of the list Write a function that adds the two numbers and returns the sum as a linked list
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
int last = ;
ListNode *p, *q, *pre;
p = l1; q= l2;
ListNode *head = p;
pre = NULL;
while(p && q){
p ->val += q->val + last;
if(p->val >= ){
last = ;
p->val -= ;
}else{
last = ;
}
pre = p;
p = p->next;
q = q->next;
}
p = NULL == q ? p : q;
pre ->next = p;
while(p && last == ){
p->val += last;
if(p->val >= ){
last = ;
p->val -= ;
}else{
last = ;
}
pre = p;
p = p->next;
}
if(last == ){
q = new ListNode();
pre ->next = q;
}
return head ;
}
};
2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an
earlier node, so as to make a loop in the linked list
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C
分析：最简洁易懂的还是数学形式的表达。设有两个指针p1、p2, p1每次向前移动一下，p2每次向前移动两个。p1到达loop 入口时，p2比p1多走了K个节点（k即为从链表入口到loop 的距离），假设T时刻两个节点相遇，则2T - T = n - k 即 T = n - K ,即相遇点到loop的入口距离为K。那么相遇点到Loop 的距离和链表头到loop 的距离相等，loop的入口点可求。
/* Link list node */
struct node
{
int data;
struct node* next;
};
// 假设输入的链表一定有环
node * FindBeginning(node * head){ if(head == NULL) return NULL;
node *p, *q;
p = head ; q = head;
do{
p = p->next;
q = q->next;
q = q->next;
}while(p != q) q = head ;
while(q != p){
p = p->next;
q = q->next ;
}
return p;
}