leetcode(1): C++ 单链表||翻转链表||相交链表||数据结构_c++力扣建立链表

背景:一篇文章总结最近学习单链表的知识；
未封装类，主要用于链表学习和leetcode以及笔试题等

1.链表结构

//定义链表结构
typedef struct ListNode {
    int data;
     ListNode *next;
     //ListNode(int x) : data(x), next(NULL) {} //初始化方法 可以不写
}ListNode ,*pListNode ;
1
2
3
4
5
6

2.链表创建||尾添加||帮助理解链表

2.1 尾添加

#include <iostream>
#include <vector>

using namespace std;
//链表定义 
typedef struct ListNode {
	int data;
	ListNode *next;
	//ListNode(int x) : data(x), next(NULL) {} //初始化方法 可以不写
}ListNode, *pListNode;

//链表头尾指针
//一般定义头指针和尾指针方便处理
pListNode g_pHead = NULL; //等效于 ListNode  *g_pHead = NULL;
ListNode *g_pEnd = NULL;

//创建链表
//添加一个数据 
//尾添加
void adddata(int a)
{
	//1.创建一个节点
	pListNode ptemp = (pListNode)malloc(sizeof(pListNode));
	ptemp->data = a;
	ptemp->next = NULL;
	//2.链接到图表中
	if (NULL == g_pHead /* || NULL == g_pEnd*/) //如果是空表
	{
		g_pHead = ptemp;
		g_pEnd = ptemp;
	}
	else //向链表最后一个节点添加
	{
		g_pEnd->next = ptemp;

	}
	g_pEnd = ptemp; //更新尾结点位置
}

int main()
{
	 g_pHead;
	 adddata(1);
	 adddata(2);
	 adddata(1);
	 adddata(2);
	 adddata(1);
	 adddata(2);

}


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

构造的链表：

2.2 头添加

// 头插法 头插法一般在大数相乘 大数幂的情景用的比较多
// 大数幂时，结果是反过来存储的，高位存储在低位节点上 以后再说
void adddataFront(int a)
{
    //1。 创建一个节点
    pListNode ptemp = (pListNode)malloc(sizeof(pListNode));
    ptemp->data = a;
    ptemp->next = NULL;
    if(g_pHead==NULL)
    {
        g_pHead = ptemp;
        g_pEnd = ptemp;
    }else //将头链接进去
    {
        ptemp->next = g_pHead;
    }
    g_pHead = ptemp;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.翻转链表||链表常用技巧（建立Pre=NULL）

3.1 翻转链表

该节主要目的就是：将 1->2->3->4->5的链表翻转成 5->4->3->2->1
这个比较简单，主要设计到了链表中经常用的一个操作：新建一个空的pre结构(相对于 previous current next )
直接上代码：

// reverse
pListNode reverse(pListNode head)
{
	//1.创建一个 前 当前 后一个  方便理解和处理
    pListNode pre = NULL, cur = head, nex = head->next;

    while(cur->next)
    {
        cur->next = pre; // 指向 前一个
        
        pre = cur; //更新 pre cur next
        cur = nex;
        nex = cur->next;
    }
    cur->next = pre; //最后一个要单独处理下
    return cur;  //翻转完成后 cur会移动到g_pEnd位置
}
//main函数
int main()
{
    g_pHead;
	 adddata(1);
	 adddata(2);
	 adddata(3);
	 adddata(4);
     adddata(5);
     pListNode ret =  reverse(g_pHead);
}




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

3.2 K个一组 翻转链表 (递归)

pListNode reverseK(pListNode head, int k)
{
    pListNode  cur = head;
    for (int i = 0; i < k-1 && cur->next != NULL; i++) //k-1 
    {
        cur = cur->next;
    }
    pListNode nexthead = cur->next;
    cur->next = NULL; 
    pListNode ret = reverse(head); //返回当前区域的头结点
    if(nexthead ==NULL)
        head->next = NULL;//如果扫描到最后一个 不连接任何链表
    else
        head ->next = reverseK(nexthead, k); // 前一块区域的尾结点指向 下一块区域的头结点
    return ret; //返回当前区域的头结点
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4. 相交链表

相交链表的实现很简单，在leetcode也有解法。
基本思想就是
同时遍历两个链表，第一次遍历时，遇到链表结尾，转为遍历另一个；这样的话两个链表指针终将"相遇"：相交链表相遇于相交点，不想交链表就是NULL`

//点（.）是用于结构体变量访问成员，
//箭头（->）是用于结构体指针访问成员。
// 该cpp中创建的都是指针 都用箭头
bool ListInter(pListNode a,pListNode b)
{
// 参考
// 作者：reals
// 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    
    if (a == NULL || b == NULL) return NULL;
    pListNode pA = a, pB = b;
    while (pA != pB) {
        pA = pA == NULL ? b : pA->next;
        pB = pB == NULL ? a : pB->next;
    }
    return pA; //不想交返回 NULL
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

github：
https://github.com/CoomCon/C-Algori
名字 1Le-ListNode