Leetcode -2

Leetcode -234.回文链表

题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：head = [1, 2, 2, 1]
输出：true

示例 2：
输入：head = [1, 2]
输出：false

提示：
链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9

我们的思路是，把链表分为两个部分，以中间的结点为分界线，分为前半部分和后半部分，如果有两个中间结点，以第一个中间结点为标准；以1->2->2->1->NULL为例，如图：

然后反转以mid为中间结点的后半部分的链表，即反转以mid->next为头的链表；如下图：

反转完成的链表：

注意反转过程中改变了链表的结构，应该在返回前把反转的部分反转回来；下面看代码以及注释：

		//找到链表前半部分的函数
		struct ListNode* SLFindMid(struct ListNode* head)
		{
		    struct ListNode* slow = head, * fast = head;
		    while (fast->next && fast->next->next)
		    {
		        slow = slow->next;
		        fast = fast->next->next;
		    }
		    return slow;
		}
		
		//反转链表的函数
		struct ListNode* SLReverse(struct ListNode* head)
		{
		    struct ListNode* curr = head, * prev = NULL;
		    while (curr)
		    {
		        struct ListNode* next = curr->next;
		        curr->next = prev;
		        prev = curr;
		        curr = next;
		    }
		    return prev;
		}
		
		bool isPalindrome(struct ListNode* head)
		{
		    //通过SLFindMid函数找到链表的前半部分，返回的是前半部分的尾指针
		    //SLReverse函数反转后半部分的链表
		    struct ListNode* mid = SLFindMid(head);
		    struct ListNode* reverse = SLReverse(mid->next);
		
		    //p1从头开始，p2从反转后后半部分链表的头开始
		    struct ListNode* p1 = head;
		    struct ListNode* p2 = reverse;
		
		    //p1和p2通过迭代比较，当p2不为空则继续比较，p2为空说明前半部分和后半部分比较完了
		    while (p2)
		    {
		        if (p1->val == p2->val)
		        {
		            p1 = p1->next;
		            p2 = p2->next;
		        }
		
		        //如果比较途中遇到不相等，返回false
		        else
		        {
		        	//把反转的后半部分反转回来，保持链表为原来的结构
		        	SLReverse(reverse);
		            return false;
		        }
		    }
		
		    //最后把反转的后半部分反转回来，保持链表为原来的结构
		    SLReverse(reverse);
		    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
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

Leetcode -160.相交链表

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 null 。

我们的思路是，分别计算两个链表的长度，再计算它们的差值gap，然后让长的那一个链表先走gap步，使它们从长度相同的结点出发比较；

		struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
		{
		    //从头遍历两个链表，计算它们的长度
		    struct ListNode* tailA = headA, * tailB = headB;
		    int lenA = 0, lenB = 0;
		    while (tailA)
		    {
		        lenA++;
		        tailA = tailA->next;
		    }
		    while (tailB)
		    {
		        lenB++;
		        tailB = tailB->next;
		    }
		
		    //gap计算它们的差值，abs为取绝对值
		    int gap = abs(lenA - lenB);
		
		    //假设A链表为长的那一个链表，B为短的链表
		    struct ListNode* longlist = headA, * shortlist = headB;
		
		    //判断A和B谁是比较长的链表
		    if (lenA < lenB)
		    {
		        longlist = headB;
		        shortlist = headA;
		    }
		
		    //让长的链表先走gap步
		    while (gap--)
		    {
		        longlist = longlist->next;
		    }
		
		    //两个链表从长度相同的结点出发比较
		    while (longlist != shortlist)
		    {
		        longlist = longlist->next;
		        shortlist = shortlist->next;
		    }
		
		    return longlist;
		}
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