阅读 76

链表操作基础

链表的基础操作我们都很熟悉,与此同时更流畅,完整,正确的解决,也是必不可少的基本功。因此我对它们做了一个总结,千万不要小看这些基础操作,熟悉它们以后你解决链表的问题将会得心应手,那么,开始吧!

先给出链表原型,后续的所有过程都基于这个结构体。

struct ListNode {
    int val;
    struct ListNode *next;
};
复制代码

四种基本操作:

创建,插入,删除,反转

  • Create
  • Insert
  • Remove
  • Reverse

1.Create

头插法

struct ListNode* createList(int n){
	struct ListNode* head = NULL;
	for (int i = 0; i < n; ++i)
	{
		struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
		//Q1
		if(!p)
			return NULL;
		//Q2
		p->val = i;
		p->next = head;
		head = p;
	}
	return head;
}
复制代码

要生成一个长度为n的链表,每个循环里,new 一个p节点,让它的下一个节点指向链表头,迭代,将这个p节点更新为链表头,返回这个链表头

头插法的特点在于你插的最后一个节点链表头,意思是你顺序访问链表时将得到一个和插入序列相反的序列。

Q1:为什么检查p?这样操作有风险吗?

因为动态内存分配存在失败的可能,当失败后返回的p是一个空指针,那么接下来两行对p的间接访问都将报错。

即使这样处理,依然存在一个问题,那就是我们是在某一次循环过程中malloc失败,我们让函数返回,意味着整个createList函数失败,并且我们在前面成功分配的那部分内存并没有回收,我们甚至都没有一个手段访问到那些已经成功分配了的内存,那么这个函数就会像一个黑洞,每一次失败的调用,都会产生一部分空间的浪费,内存泄漏就极有可能会发生。因此,更周全的做法也许是在分配失败时,我们在函数内部free掉之前已经的内存。

不过好在这种情况,在我们写到的函数里基本不会发生,我们可以放心使用上面的做法生成一个链表。

Q2:有其他的赋值方法吗?最好方便测试?

当然,我们可以根据我们对链表的操作对它进行修改。 例如我们想对测试链表排序,我们可以让i换成rand。 我们想要删除链表重复元素,我们可以让它等于i / 3,这样会产生连续三个相同值的节点。 我们想产生1-2-3-4-5而不是5-4-3-2-1那可以让它变成n-i

尾插法

struct ListNode* createList(int n){
	struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* tail = head;
	for (int i = 0; i < n; ++i)
	{
		struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
		if(!p)
			return NULL;
		p->val = i;
		p->next = NULL;
		tail->next = p;
		tail = p;
	}
    //Q1
	return head->next;
}
复制代码

与头插法相反,尾插法将每一个新的p节点当作是链表的尾节点,它们的next域统统初始化为NULL,迭代的是tail,每一次插入后让tail指向新的p,对照着头插法,你很快会弄清楚尾插的原理。

Q1:为什么返回的是head->next?

因为我们第一次循环时,tail实际上同时也是head,这时的这第一个p应该就是我们所希望返回的链表头,head->next便是这一个p,所以我返回head->next。

2.Insert

插入的关键在于找到待插入位置之前的那个节点,改变它的next域,让它指向插入的新节点p。因此,特殊的位置往往发生在链表头,它之前没有节点了,是NULL。我们需要对这种特殊情况考虑。当然,如果一个链表有一个val域无意义的头节点dummyHead,这个问题也就不存在了。下面的便是一个有头节点的例子,注意,有头节点的链表在访问时都要先往前推进一个。

我们来看LeetCode上关于基础操作的一道题:707.Design Linked List.

题目描述过长我就不引用了,上面链接过去看吧。

我的解答:

MyLinkedList* myLinkedListCreate() {
    MyLinkedList* p = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = -1;
    p->next = NULL;
    return p;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
	if(index < 0)
		return -1;
	if(!obj->next)
		return -1;
	MyLinkedList* p = obj->next;
    for (int i = 0; i < index; ++i)
    {
    	p = p->next;
    	if(!p)
    		return -1;
    }
    return p->val;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
	MyLinkedList* p = (MyLinkedList*)malloc(sizeof(MyLinkedList));
	if(!p)
		return;
	p->val = val;
	p->next = obj->next;
	obj->next = p;   
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList* p = obj;
    while(p->next){
    	p = p->next;
    }
    MyLinkedList* newp = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    if(!newp)
		return;
    newp->val = val;
    newp->next = NULL;
    p->next = newp;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
	if(index < 0)
		return;
	MyLinkedList* p = obj;
    for (int i = 0; i < index; ++i)
    {
    	p = p->next;
    	if(!p)
    		return;
    }
    MyLinkedList* newp = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    if(!newp)
		return;
    newp->val = val;
    newp->next = p->next;
    p->next = newp;
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if (index < 0)
    	return;
    MyLinkedList* tmp, *p = obj;
    if(!obj->next)
    	return;
    for (int i = 0; i < index; ++i)
    {
    	//ensure the delete node is not null
    	if(!p->next->next)
    		return;
    	p = p->next;
    }
    //p is before the node tobe deletes 
    //normal
    tmp = p->next;
    p->next = p->next->next;
    free(tmp);

}

void myLinkedListFree(MyLinkedList* obj) {
	MyLinkedList* tmp;
	while(obj){
		tmp = obj;
		obj = obj->next;
		free(tmp);
	}   
}

void myLinkedListPrint(MyLinkedList* obj){
	MyLinkedList* p = obj->next;
	while(p){
		printf("%d->", p->val);
		p = p->next;
	}
	printf("NULL\n");
}
复制代码

3.Remove

其实删除或许完全可以和插入放在一起,它的重点仍然是找到它的前一个节点,如果删除的是第一个元素,那么这是一种特殊情况,它的前面没有节点,应该单独考虑。

那么不把它们放在一起的原因是什么呢?删除涉及到空间的回收,也就是free的正确使用,这将是一个很容易出错的地方。关于free, 我会在最后再提到它。

例子可以参考上面代码里的myLinkedListDeleteAtIndex()

来做几道题吧!

203.Remove Linkedlist Elements
Problems
Remove all elements from a linked list of integers that have value val.

Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5

第一种做法,定义一个显示的pre指针,并保证它的指向始终指向删除元素的前一个位置,那么显然,对第一个元素的删除是一种特殊情况。

struct ListNode* removeElements_2(struct ListNode* head, int val) {
	struct ListNode* cur = head, *pre = NULL, *tmp;
	while(cur != NULL){
		if(cur->val == val){			
			if(pre != NULL)
				pre->next = cur->next;			
			else
				head = head->next;	
			tmp = cur;						
			cur = cur->next;
			free(tmp);	
		} else{
			pre = cur;
			cur = cur->next;
		}		
	}	
	return head;   
}
复制代码

对于这种做法,我在第7行对这种情况进行了处理。那就是改变head的指向而不是改变pre->next,因为你无法对一个NULL指针进行->运算,因为他实际上包含了指针的间接访问,pre->next = (*pre).next,这一点你在使用->它的时候应该很清楚才是。

关于空间释放,这里要释放的当然是cur节点,因为要删除的就是它,那么为什么不直接free(cur)呢?free(cur)之后,我们无法访问cur->next,因为它已经被释放掉了,那我们怎么推进cur呢?答案是设置一个临时指针,先将之前的cur节点记录下来,我们在访问过后,释放那个tmp节点,就非常安全了。

另一种做法可以避免删除头元素的特殊情况,它使用到了指针的指针&运算符,取地址运算符也算是C的一大特性了,同时,这个例子也是指针的指针的经典运用

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode ** p = &head, * tmp;
	while(*p){
		if((*p)->val == val){
			tmp = *p;
			*p = (*p)->next;
			free(tmp);
		}
		else
			p = &((*p)->next);
	}
	return head;   
}
复制代码

该算法中用来推进的是*p,我们发现在删除时我们改变了*p,这实际上操纵的就是当前元素,意思是我们的前一个元素无需做出改变,依然指向它原先指向的节点,而我们对这个节点直接做出改变,让它变成它的下一个节点,再释放掉它,删除就完成了。那么为什么它可以避免删除头元素的特殊情况呢?因为我们根本就不用考虑前一个节点了。

要改变一个指针p的内容我们通过*p实现,那么要改变一个指针p,我们需要使用*pp,其中pp = &p,pp实际上就是一个指针的指针。

那么像p1 = p2这样又代表着什么呢?为了弄清楚上面的内容,再举一个例子。

int a = 3, b = 2;
a = b;
b = 4;
复制代码

现在a = ?显然 a = 2。 只是把b当前的值赋给了a。p1 = p2同样也只是让p2当前的值赋给了p2,p1和p2之间在这行语句后就没什么联系了。

再来一道, 83.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.

Example 1:
Input: 1->2->3->3->4->4->5 Output: 1->2->5

Example 2:
Input: 1->1->1->2->3 Output: 2->3

我的解答:

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(!head || !head->next)
        return head;
    struct ListNode* fakeNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    fakeNode->next = head;
    struct ListNode* pre = fakeNode, *tmp;
    //pre是第一个uinique元素出现的前一个节点
    while(head){
        //释放了这些节点的内存,推进了head,但没有改变指向
        while(head->next && head->val == head->next->val){
            tmp = head;
            head = head->next;
            free(tmp);
        }
        //说明head是unique的,直接往前推进
        if(pre->next == head){
            pre = pre->next;
            head = head->next;
        }
        //一次性改变pre->next,pre不推进
        else{
            pre->next = head->next;
            free(head);
            head = pre->next;
        }
    }
    return fakeNode->next;    
}
复制代码

这同样是一个增加头节点避免特殊情况的例子,fakeNode就是这个头节点。
需要注意的是,我采取的策略里并不是每删除一个元素就改变它前一个节点的指向,而是在推进到不等于当前连续的这些值时,一次性改变pre->next让它直接指向下一个,也就是值开始不同的那个节点。

关于删除,leetcode上还有这些题可以参考:237,83,707,82。

4.Reverse

关于反转链表,我会很自然的想到头插法,那么的确这样,你完全可以用头插法的视角来看待下面这个例子。

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* tmpHead = NULL;
    struct ListNode* p = head;
    while(p != NULL){
    	struct ListNode* tmp = p->next;
    	p->next = tmpHead;
    	tmpHead = p;
    	p = tmp;
    }
    return tmpHead;
}
复制代码

很简单,对不对,就是遍历原链表,再将节点依次用头插法的方式插入。值得注意的是,现在链表的结构已经改变,我们做的是in-place,也就是在原有空间上做出的修改,我们现在的head已经变成了什么?

事实上,观察一个链表的结构有没有被破坏,我们只用看对链表的访问过程中我们有没有对p->next有没有改变,即使p不是head本身,在本例中我们第一次循环时便改变了它,这个时候head->next变成了NULL,对,它变成了尾节点。改变p对原链表的结构实际上是没有影响的。想想为什么?

再看一例:
25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example: Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5

思路:一次选择k个元素一组,这一组中第一个元素设为first,然后将这个组反转kHead是这个反转子串的头,设立一个pre指针,始终指向反转后最后一个元素,开始时pre指向一个dummyHead,也就是这里的head2。每次循环结束前让pre->next指向新的kHead

我的解答:

struct ListNode* reverseKGroup(struct ListNode* head, int k) 
{
	int length = 0; 
	struct ListNode* p = head;
	while(p){
		p = p->next;
		length += 1;
	}	
	if(length < k)
		return head;
	int res_node = length;
	struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode)); 
	struct ListNode* pre = head2;
	struct ListNode* kHead = NULL, *tmp, *first = NULL;
	while(res_node >= k){
		int n = k;
		kHead = NULL;
		first = NULL;
		while(n--){
			first = first?first:head;
			tmp = head->next;
			head->next = kHead;
			kHead = head;
			head = tmp;
		}
		pre->next = kHead;
		pre = first;
		res_node -= k;
	}
	pre->next = head;
	return head2->next;
}
复制代码

dummyHead真香~

更多关于reverse的还有成对交换啊,指定位置反转啊,利用反转花式改变链表结构啊,利用反转判断回文啊,leetcode上都有对应的题目,可以按tag去搜索挑战一下。

关注下面的标签,发现更多相似文章
评论