当前位置:   article > 正文

1.1 LeetCode总结(线性表)_链表类_leetcode c语言 链表 库

leetcode c语言 链表 库

编程总结

每每刷完一道题后,其思想和精妙之处没有地方记录,本篇博客用以记录刷题过程中的遇到的算法和技巧

在这里插入图片描述

203. 删除链表的节点

在这里插入图片描述

法一:需要单独处理头结点和非头结点

struct ListNode *deleteNode(struct ListNode *head, int val)
{
	struct ListNode *tmp = head;
	struct ListNode *pre = NULL;
	struct ListNode *cur = NULL;
	int    index = 0;

	while (tmp->next != NULL) {
		if (tmp->val == val) {
			break;
		}
		tmp = tmp->next;
		index++;
	}
	cur = tmp;
	// 1. 删除的是 head 节点.
	if (index == 0) { 
		struct ListNode *node = tmp->next;
		tmp->next = NULL;
		return node;
	}
	// 2. 否则,非 head 节点,那就先找到 pre 节点.
	tmp = head;
	while (index > 1) {
		tmp = tmp->next;
		index--;
	}
	pre = tmp;
	pre->next = cur->next;
	cur->next = NULL;
	cur->val  = 0;
	return 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

法二:创建虚拟头结点,来处理

struct ListNode *removeElements(struct ListNode *head, int val)
{
    struct ListNode *dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode *temp = dummyHead;
    while (temp->next != NULL) {
        if (temp->next->val == val) {
            temp->next = temp->next->next;
        } else {
            temp = temp->next;
        }
    }
    return dummyHead->next;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

***. 链表基本操作

typedef struct ListNode_t {
	int val;
	struct ListNode_t *next;
} ListNode;

// 1.创建链表
ListNode *ListCreate() {
	// 在链表的第一个结点之前会额外增设一个结点,头结点
	ListNode *head = (ListNode *)malloc(sizeof(ListNode));
	if (head == NULL) {
		return NULL;
	}
	head->next = NULL;
	head->val = 0; // 头结点的val用来指示链表长度

	return head;
}
// 2.获取链表中第index个节点的索引值,如果索引无效,则返回-1
int ListIndexGet(ListNode *obj, int index)
{
	int cnt = 0;
	ListNode *tmp = obj->next; // 手法:  因为我们是以首元结点开始index为0,所以要obj->next以首元开始
							   // 而不是 ListNode *tmp = obj; 
	while (tmp) {
		if (index == cnt) {
			return tmp->val;
		}
		cnt++;
		tmp = tmp->next;
	}
	return -1;
}

// 首元结点:链表中第一个元素所在的结点,它是头结点后边的第一个结点
/* 在链表的第一个元素之前添加值为val的节点。插入后,新节点将成为链表的第一个节点 */
/* obj -> node1 -> node2 */
/* obj -> newNode  -> node1 -> node2 */
void ListAddAtHead(ListNode *obj, int val)
{
	ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
	if (newNode == NULL) {
		return;
	}
	obj->val++; // 记录链表长度
	newNode->val = val;
	newNode->next = obj->next;
	obj->next = newNode;
}

/*  将值为val的节点附加到链表的最后一个元素 */
/*  head  -> node1 -> node2 */
/*  head  -> node1 -> node2 -> tail */
void ListAddAtTail(ListNode *obj, int val)
{
	ListNode *tail = (ListNode *)malloc(sizeof(ListNode));
	ListNode *tmp  = obj;
	if (tail == NULL) {
		return;
	}
	obj->val++; // 记录链表长度
	tail->val = val;
	tail->next = NULL;
	while (tmp->next) {
		tmp = tmp->next;
	}
	tmp->next = tail;
}

/* 在链表的索引节点之前添加一个值为val的节点。如果索引等于链表的长度,
   则节点将附加到链表的末尾。如果索引大于长度,则不会插入节点 */
/* obj -> node1 -> node2 */
/* obj -> node1 -> newNode -> node2 */
void ListAddAtIndex(ListNode *obj, int index, int val)
{
	int cnt = 0;
	if (index == obj->val) {
		ListAddAtTail(obj, val);
		return;
	} else if (index > obj->val) {
		return;
	}
	ListNode *tmp = obj;
	ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
	newNode->val = val;
	while (tmp) {
		if (cnt == index) {
			break;
		}
		tmp = tmp->next;
		cnt++;
	}
	obj->val++; // 记录链表长度
	newNode->next = tmp->next;
	tmp->next = newNode;
	return;
}

/* 如果索引有效,请删除链表中的第index个节点 */
/*  head  -> node1 -> node2 -> node3 */
/*  head  -> node1 -> node3          */
void ListDeleteAtIndex(ListNode *obj, int index)
{
	ListNode *node = NULL;
	ListNode *tmp = obj;
	int cnt = 0;
	while (tmp) {
		if (cnt == index) {
			break;
		}
		cnt++;
		tmp = tmp->next;
	}
	if (tmp->next == NULL) { // 删除的是最后的NULL,直接返回,手法
		return;
	}
	obj->val--;
	node = tmp->next;
	tmp->next = node->next;
	free(node);
}
/*  head  -> node1 -> node2 -> node3 */
void ListFree(ListNode *obj)
{
	ListNode *tmp = obj;
	ListNode *freeNode;

	while (tmp) {  // 释放头结点->首元结点内的
		freeNode = tmp;
		tmp = tmp->next;
		freeNode->next = NULL;
		freeNode->val = 0;
		free(freeNode);
	}
}
  • 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
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134

206. 反转链表

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

下图一到图二进行了四个步骤的变化:
在这里插入图片描述在这里插入图片描述

法一:双指针

struct ListNode *reverseList(struct ListNode *head) {
	ListNode *pre = NULL; // 需要指向前一个元素的指针,因为要转向,所以先来一个pre
	ListNode *cur = head;
    while (cur != NULL)   // cur移动到NULL,此时pre就是新链表的第一个节点
    {
        // 1. 转向
		ListNode *next = cur->next; // 保存 cur 的 next 节点
        cur->next = pre;  // cur新的next指向pre,也就是节点反向,同时,此时cur之前的next就断了,也是为什么要先保留cur->next 的原因  
        // 2. 平移 继续之前的操作,先保留next,然后反向cur->next,然后平移
        pre = cur;        // 平移pre节点
        cur = next;       // 平移cur节点
    }
    return pre; // 新链表的头结点,pre
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

法二:数组记录法
因为题目其实只看数值是否反转了,所以也可以使用将链表存放到数组里,再反转的思路解题:

struct ListNode *reverseList(struct ListNode *head) 
{
	int capacity;
	struct ListNode *tmp = head;
	int index = 0;

	// 1.计算capacity
	while (tmp != NULL) {
		index++;
		tmp = tmp->next;
	}
	capacity = index;
	int *res = (int *)malloc(sizeof(int)*capacity);
	index = 0;
	tmp = head;
	// 2.将链表的值转移到数组里
	while (tmp != NULL) {
		res[index++] = tmp->val;
		tmp = tmp->next;
	}
	tmp = head;
	index = index - 1;
	// 3.反转赋值回链表里
	while (tmp != NULL) {
		tmp->val = res[index--];
		tmp = tmp->next;
	}
	free(res);

	return 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

19. 删除链表的倒数第 N 个结点

在这里插入图片描述
思路:
这题常规解决要处理的思路是不好删除首节点,比如:链表 [1,2] 想删除倒数第2个节点 1.

在对链表进行操作时,一种常用的技巧是添加一个哑节点(dummy node),它的 next 指针指向链表的头节点。这样一来,想操作头节点一样的处理手法即可,不需要额外处理。
dummy->next = head; 和 203. 删除链表节点 一个手法~

在这里插入图片描述

// 特殊处理如果删除的首节点的情况,比如 [1,2] 删除倒数第2个节点.  
int getLength(struct ListNode *head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}
// 如果要删除头结点,那么会找到dummy节点,通过将 cur->next = cur->next->next 来删除头节点
struct ListNode *removeNthFromEnd(struct ListNode *head, int n) {
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    int length = getLength(head);
    struct ListNode *cur = dummy;
    // 倒数第N个,即正数第 len-n 个, 遍历到第 len−n+1 个节点进行处理
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next; // 删除原来的cur->next 即 len-n 个节点
    struct ListNode *ans = dummy->next; 
    free(dummy);
    return ans;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {

    int length_l1 = 0;
    int length_l2 = 0;
    struct ListNode *head = NULL;
    struct ListNode *res  = NULL;
    struct ListNode *l1_t  = l1;
    struct ListNode *l2_t  = l2;

    if (l1 == NULL && l2 == NULL) {
        return NULL;
    }
    // 1.计算 l1 l2 的length
    while(l1_t != NULL) {
        l1_t = l1_t->next;
        length_l1++;
    }
    while(l2_t != NULL) {
        l2_t = l2_t->next;
        length_l2++;
    }
    // 新建一个新的链表
    head = (struct ListNode *)malloc((length_l1 + length_l2)*sizeof(struct ListNode ));
    res  = head;

    while (l1 != NULL || l2 != NULL) {
        // 特殊情况处理
        if (l1 == NULL) {
            head->next = l2;
            l2 = l2->next;
            head = head->next;
        }
        else if (l2 == NULL) {
            head->next = l1;
            l1 = l1->next;
            head = head->next;
        }
        // 2.哪个小赋值到新的链表里去
        else if (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                head->next = l1;
                head = head->next;
                l1   = l1->next;
            } else {
                head->next = l2;
                head = head->next;
                l2   = l2->next;
            }
        }
    }
    return res->next;
}
  • 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
  • 49
  • 50
  • 51
  • 52

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

	// 注意是 malloc(sizeof(struct ListNode));
	// 不是   malloc(sizeof(struct ListNode *));
	// 区别是 malloc 一个指针指向 大小为 ListNode
	struct ListNode *head = NULL;
	head = (struct ListNode *)malloc(sizeof(struct ListNode));
  • 1
  • 2
  • 3
  • 4
  • 5

83. 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次

struct ListNode *deleteDuplicates(struct ListNode *head)
{
	struct ListNode *cur = head;
	int value = 0;
	int value_next = 0;
	
	while (cur != NULL && cur->next != NULL) {
		value = cur->val;	
		value_next = cur->next->val;
		if (value == value_next) {
			cur->next = cur->next->next; // 注意不是:cur = cur->next->next;
		} else {
			cur = cur->next;
		}
	}

	return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

160. 相交链表 – 两个链表的第一个公共节点

>将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p = headA;
    struct ListNode *q = headB;
    while(p!=q)
    {
        if(p)
            p = p->next;
        else
            p = headB;
        if(q)## 标题
            q = q->next;
        else
            q = headA;
    }
    return q;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述
–相交链表:“只要我们走一走彼此走过的路,就一定会相遇”
况一:两个链表相交
在这里插入图片描述

86. 分隔链表

给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。
在这里插入图片描述

 struct ListNode {
      int val;
     struct ListNode *next;
 };

struct ListNode *partition(struct ListNode *head, int x)
{
	struct ListNode *p1 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *p2 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *head_tmp = head;
	struct ListNode *p1_tmp = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *p2_tmp = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	p1->next = NULL;
	p2->next = NULL;
	p1_tmp = p1;
	p2_tmp = p2;

	while (head_tmp != NULL) {
		if (head_tmp->val < x) {
			p1_tmp->next = head_tmp;
			p1_tmp = head_tmp;
		}
		else {
			p2_tmp->next = head_tmp;
			p2_tmp = head_tmp;
		}
		head_tmp = head_tmp->next;
	}
	// contact
	p2_tmp->next = NULL;
	p1_tmp->next = p2->next;

	return p1->next;
}

int main(void)
{
	struct ListNode *value0 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value1 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value2 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value3 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value4 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value5 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *res = (struct ListNode *)(malloc(sizeof(struct ListNode)));

	value0->val = 1;
	value1->val = 4;
	value2->val = 3;
	value3->val = 2;
	value4->val = 5;
	value5->val = 2;
	value0->next = value1;
	value1->next = value2;
	value2->next = value3;
	value3->next = value4; 
	value4->next = value5;
	value5->next = NULL;
	res = partition(value0, 3);
}
  • 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
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

剑指 Offer 06. 从尾到头打印链表

在这里插入图片描述

int *reversePrint(struct ListNode *head, int *returnSize) 
{
	int len = 0;
	struct ListNode *tmp = head;
	int i = 0;

	while (tmp != NULL) {
		len++;
		tmp = tmp->next;
	}
	*returnSize = len;
	int *resTmp = (int *)malloc(sizeof(int)*len);
	int *res = (int *)malloc(sizeof(int)*len);
	tmp = head;

	while (tmp != NULL) {
		resTmp[i++] = tmp->val;
		tmp = tmp->next;
	}
	i = i - 1;
	for (int j = 0; j < len; j++) {
		res[j] = resTmp[i--];
	}
	free(resTmp);

	return res;
}
  • 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

234. 回文链表

在这里插入图片描述
回文链表和回文数一样,是指完全可以中心对称的链表。
思路一:
一共为两个步骤:
复制链表值到数组列表中。
使用双指针法判断是否为回文。
思路二:
我们可以将链表的后半部分反转(修改链表结构),然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。
从实现上,第一种思路易于实现

bool isPalindrome(struct ListNode *head) 
{
	struct ListNode *tmp = head;
	int index = 0;
	int capacity = 0;
	int j;

	// 1. 计算链表容量 capacity.
	while (tmp != NULL) {
		tmp = tmp->next;
		index++;
	}
	capacity = index + 1;
	index = 0;
	tmp   = head;

	// 2. 将链表转移至数组.
	int *res = (int *)malloc(sizeof(int)*capacity);
	while (tmp != NULL) {
		res[index++] = tmp->val;
		tmp = tmp->next;
	}
	// 3.判断数组的值是否回文.
	j = index - 1;
	for (int i = 0; i <= j; ++i) {
		if (res[i] != res[j--]) {
			return false;
		}
	}
	free(res);

	return true;
}
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/618093
推荐阅读
相关标签
  

闽ICP备14008679号