stanford cs linked list problems

Posted on |

background

stanford cs gives me some confidence to deal with linked list.

linked list basics

basic pointers as well as previous blog:

  • a pointer stores a reference to another variable(pointee). what stored inside pointer is an reference to its pointee’s type.

  • NULL pointer, points to nothing.

  • pointer assignment p=q, makes the two pointers point to the same pointee, namely the two pointers point to the same pointee memory.

it’s a good habit to remember to check the empty list case.

define the Linked-List structure:

1
2
3
4
5
6
struct ListNode {
	int val ;
	ListNode *next;
	ListNode(int x): val(x), next(NULL){}
};
typedef ListNode node_ ;
  • iterate over the list with a local pointer
1
2
3
4
5
6
node_ *current = head ;
while(current){
	current = current->next;
}
for(current=head; current!=NULL; current=current->next){};
  • push a new node to the front of the list 
1
2
3
4
5
6
7
8
9
10
11
12
13
void Push(ListNode** headRef, int val){
	ListNode newNode = new ListNode(val);
	newNode.next = *headRef ;
	*headRef = newNode ; 
}
``` 
* changes the head pointer by a reference pointer
```c++
void changetoNull(ListNode** head){
	*head = NULL;
}
  • build up a list by adding nodes at its head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
ListNode* AddatHead(){
	ListNode *head = NULL ;
	for(int i=1; i<5; i++){
		Push(&head, i);
	}
	return head;
}
``` 
which gives a list {4, 3, 2, 1} 
* build up a list by appending nodes to the tail
```c++
ListNode* BuildwithSpecialCase(){
	ListNode* head = NULL ;
	ListNode* tail ; 
   Push(&head, 1);
   tail = head ; 
   for(int i=2; i<5; i++){
       Push(&(tail->next), i);
       tail = tail->next;
   }
   return head; 
}
``` 
which gives a list {1, 2, 3, 4}
* build up a list with dummy node 
```c++
ListNode* BuildWithDummy(){
   ListNode dummy = new ListNode(0);
   ListNode* tail = &dummy ; 
   for(int i=1; i<5; i++){
   		Push(&(tail->next), i);
   		tail = tail->next;
   	}
   	return dummy.next ; 
}

which returns a list {1, 2, 3, 4}

  • appendNode(), add new node at the tail
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ListNode* appendNode(ListNode** headRef, int val){
	ListNode *current  = *headRef ;
	ListNode newNode = new ListNode(num);
	if(!current){
		current = &newNode ;
	}else{
		while(current->next){
			current = current->next ;
		}
		current->next = &newNode ;
	}
}
``` 
* copyList()
```c++
ListNode* copyList(ListNode* head){
	ListNode *current = head ;
	ListNode *newList = NULL ;
	ListNode *tail = NULL ;
	
	while(current){
		if(!newList){
			newList = &(new ListNode(current->val));
			tail = newList ;
		}else{
			tail->next = &(new ListNode(current->val));
			tail = tail->next ; 
		}
	}
	
	return newList ; 
}
  • copyList() recursive 
1
2
3
4
5
6
7
8
ListNode* CopyList(ListNode* head){
	if(!head) return NULL;
	else{
		ListNode *current = head ;
		ListNode *newList = &(ListNode(current->val));
		newList->next = CopyList(current->next);
	}
}

linked list problems further

  • InsertNth()
1
2
3
4
5
6
7
8
9
10
void insertNth(node_ **head, int index, int data){
	if(index==0) Push(head, data);
	else{
		node_ * cur = *head ;
		for(int i=0; i<index-1; i++){
				cur = cur->next ;
		}	
		Push(&*cur->next), data);
	}
}
  • sortedInsert()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// be notified, here we using **, to use the pointer of the head, as the head node may be updated  
void sortedInsert(node_ **head, node* newNode){
	if(*head == NULL || head->val >= newNode->val){
		newNode->next = *head;
		*head = newNode;
	}else{
		node_ *cur = *head ;
		while(cur->next && cur->next->val < newNode->val){
			cur = cur->next;
		} 
		newNode->next = cur->next ;
		cur->next = newNode ;
	}
}
//with dummy head
void sortedInsert(node_ **head, node* newNode){
	node_ dummy(0);
	dummy.next = *head ; 	
	node_ *cur = &dummy ;
	while(cur->next && cur->next->val < newNode->val){
		cur = cur->next;
	}
	newNode->next = cur->next ;
	cur->next = newNode ;
	*head = dummy->next;
}
  • insertSort()

given as unsorted list, and output with an sorted list

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(node_ ** head){
	node_ *result = NULL ;
	node_ *cur = *head ;
	node_ *next ;
	while(cur){
		next = cur->next ;  // ticky- note the next pointer, before we change it
		sortedInsert(result, cur);
		cur = next ;
	}
	*head = result ;
}
  • append()

append list b to the end of list a 

1
2
3
4
5
6
7
8
9
10
11
12
void append(node_ **a, node_ **b){
	node_ * cur ;
	if( *a == NULL){ *a = *b ;}
	else{
		cur = *a ;
		while(cur->next){
			cur = cur->next;
		}
		cur->next = *b ;
	}
	*b = NULL ; 
}
  • frontBackSplit()

given a list, split it into two sublists: one for the front half, one for the back half

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void frontBackSplit(node_ **head, node_ **front, node_ **back){
	int len = length(head);
	node_ *cur = *head ;
	if(len < 2){
		*front = *head;
		*back = NULL ;
	}else{
		int half = len/2; 
		for(int i=0; i<half-1; i++){
			cur = cur->next;
		}
		*front = *head;		
 		*back = cur;
		cur = NULL ;
	}
}
void frontBackSplit2(node_ **head, node_ **front, node_ **back){
	node_ *fast, *slow ;
	if(*head == NULL || (*head)->next == NULL){
		*front = *head ;
		*back = NULL ;
	}else{
		slow = head;
		fast = head->next ;
		while(fast){
			fast = fast->next;
			if(fast){
				fast = fast->next;
				slow = slow->next;
			}
		}
		*front = *head;
		*back = slow->next ;
		slow->next = NULL ;
	}
}
  • removeDuplicates()

remove duplicated node from a sorted list 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void removeDuplicates(node_ ** head)
{
	node_ *slow, *fast ;
	if(head == NULL || head->next == NULL){
 		return ;
        }
	slow = *head ;
	fast = (*head)->next ;
	while(fast){
		if(slow->val == fast->val){
			node_ * needfree = fast ;
			fast = fast->next ;
			free(needfree); 
		}else{
		   slow = slow->next;
		   fast = fast->next;
		}
	}
}
void removeDuplicate(node_ **head){
	node_ *cur = *head;
	if(cur==NULL) return ;
	while(cur->next){
		if(cur->val == cur->next->val){
			node_ *nextNext = cur->next->next ;
			free(cur->next);
			cur->next = nextNext;
		}else{
			cur = cur->next;
		}
	}
}
  • moveNode()

given two list, remove the front node from the second list, and push it onto the front of the first.

// a = {1, 2, 3}; b = {1, 2, 3} => a={1, 1, 2, 3}, b={2, 3}

1
2
3
4
5
6
void moveNode(node_ **dest, node_ **source){
	node_ *newNode = *source ; 
	*source = newNode->next ; 
	newNode->next = *dest ;
	*dest = newNode ; 
}
  • alternatingSplit()

given a list, split its nodes into two shorter lists. if we number the elements 0, 1, 2, …, then all the even elements go to the first sublist, and all the odd elements go to tthe second

1
2
3
4
5
6
7
8
9
10
11
12
13
void alternatingSplit(node_ *source, node_ **ahead, node_ **bhead){
	node_ *a = NULL ;
	node_ *b = NULL ;
	node_ *cur = *source ;
	while(cur){
		moveNode(&a, &cur);
		if(cur){
			moveNode(&b, &cur);
		}
	}
	*ahead = a ;
	*bhead = b;
}
  • shuffleMerge()

given two list, merge their nodes together to make one list, takign nodes alternatively between the two lists 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
node_* shufflMerge(node_ *a, node_ *b){
	node_ *res = NULL ;
	int i=0;
	while(a || b){
		if(i % 2 == 0 && a){
			moveNode(&res, &a);
		}else if(b){
			moveNode(&res, &b);
		}
	}
} //but this gives the tail to front order
node_* shufflMerge2(node_ *a, node_ *b){
	node_ dummy(0);
	node *tail = &dummy ;
	while(1){
		if(a==NULL){
			tail->next = b;
			break ;
		}else if(b == NULL){
			tail->next = a;
			break;
		}else{
			tail->next = a ;
			tail = a ;
			a = a->next ;
			tail->next = b;
			tail = b;
			b = b->next;
		}
	}
	return dummy.next ;
}
// recursive ?
node_* shufflMerge3(node_ *a, node_ *b){
	node_ *res ;
	node_ *recur ; 
	if(a==NULL) return b ;
	else if(b=NULL) return a ;
	else{
		recur = shuffleMerge3(a->next, b->next);
		res = a ;
		a->next = b ;
		b->next = recur ;
		return res;
	}
}
  • sortedMerge()

given two sorted in incresing order listes, merge into one in increasing order 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
node_ *sortedMerge(node_ *a, node_ *b){
	node_ dummy(0);
        node_ *tail = &dummy ;
	dummy.next = NULL ;
	while(1){
		if(a==NULL){
			tail->next = b ;
			break;
		}else if(b==NULL){
			tail->next = a;
			break ;
		}
		if(a->val <= b->val){
			moveNode(&(tail->next), &a);
		}else{
			moveNode(&(tail->next), &b);
		}
		tail = tail->next; 
	}
	return dummy.next ;
}
// how this works?
node_ *sortedMerge2(node_ *a, node_ *b){
	node_ *result = NULL ;
	if(a==NULL) return b;
	if(b==NULL) return a;
	if(a->val <= b->val){
		result = a;
		result->next = sortedMerge2(a->next, b);
	}else{
		result = b;
		result->next = sortedMerge2(a, b->next);
	}
	return  result;
}
  • mergeSort()
1
2
3
4
5
6
7
8
9
10
11
12
13
void mergeSor(node_ ** headRef){
	node_ *head = *headRef ;
	node_ *a, *b;
	if( (head==NULL) || (head->next == NULL)){
		return ;
	}
	frontBacksplit(head, &a, &b);
	mergeSort(&a);
	mergeSort(&b);
	*headRef = sortedMerge(a,b):
}
  • reverse()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void reverse(node_ **head){
	node_ *res = NULL;
	node_ *cur = *head ;
	node_ *next ;
	while(cur){
		next = cur->next;
		cur->next = res ;
		res = cur ;
		cur = next ; 
	}
	*head = res;
}
  • recursive reverse()

// concerned 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void recursiveReverse(node_ **head){
	ndoe_ *first, *rest ;
	if(*head == NULL) return ;
	first = *head ;
	rest = first->next ;
	if(rest == NULL) return ;	
	recursiveReverse(&rest);
	first->next->next = first ;
	first->next = NULL ;
	
	*head = rest ;
}

reference

linked list problems

linked list basics from standford cs