LeetCode-链表问题

image-20220227131753050

1.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

这次删除的是链表，链表删除元素比较方便，但要注意元素边界

思路： 先提出剔除 链表前部分符合条件元素，找真正的起点
从起点开开始遍历，查看下一个元素是否符合，符合跳过，更改指针方向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *removeElements(ListNode *head, int val) {
   while (head->next != nullptr && head->val == val) {  //看前部分是否符合条件
     head = head->next;
   }
   ListNode *cur = head;  //真正的head， 用cur去操作，head是我们要的结果
   while (cur != nullptr && head->next != nullptr) {
     if (cur->next->val == val) {    //如果符合 跳过指向下下个
       cur->next = cur->next->next;  
     } else {
       cur = cur->next;   //不符合，直接下一个i
     }
  return head;  //返回的是head，cur 是用来操作链表的
   }
 }

2. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表 (经典题目了)

思路1： 建一个虚拟的头节点，然后遍历链表，改变元素指针指向（指向虚拟节点）

思路2： 用栈的特性，遍历链表入栈，出栈一个一个链接起来

1
2
3
4
5
6
7
8
9
10
11
12
ListNode *reverseList(ListNode *head) {
ListNode * vhead = nullptr;
ListNode *cur = nullptr;
while (head != nullptr) //遍历链表
{
	cur = head;        //cur 指向当前元素
	head = head ->next; // head 指向下一个元素，为下一次遍历做准备
	cur->next = vhead; // 当前元素指向虚拟节点
	vhead = cur;       //更新虚拟节点的位置，保证下次 元素指向的还是头节点
}
return vhead;    // 	遍历结束  最后 执行代码是  vhead = cur; 所以vhead执行最后一个也是反转后第一个
 }

3. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路： 因为两两交换，所以每次都选两个节点，开始的时候用一个虚拟的节点作为头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* swapPairs(ListNode* head) {
    if (head == nullptr) {
      return nullptr;
    }
    ListNode *dyHead = new ListNode(0); 
    dyHead->next = head;
    ListNode *cur = dyHead; //到了这里  cur和dyhead控制着的相同的节点，并且该节点指向链表头部
    // 下个节点和 下下个节点是否存在
    while (cur->next && cur->next->next) {  
      ListNode *t1 = cur->next;  //下个节点   t1 对应 a 
      ListNode *t2 =cur->next->next; //下下个节点   t2 对应 b
      //改变节点指向 如下图所示 
      t1->next = t2->next;  //3   
      t2->next = t1;   // 2
      cur->next= t2;   // 1
      cur = cur->next->next;  //为下次交换节点做为准备
    }
    return dyHead->next;
}
image-20220228153050186

4.链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

思路： A 和 B 都同时走

​ 若相交，链表A： a+c, 链表B : b+c
​ a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。
​ 若不相交，a+b = b+a 。因此相遇处是NULL 

1
2
3
4
5
6
7
8
9
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	ListNode *fast = headA;
	ListNode *slow = headB;
	while (fast != slow) {
  		fast = (fast != nullptr ? fast->next : headB);
  		slow = (slow != nullptr ? slow->next : headA);
	}
	return fast;
}

5. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

img

反转链表升级版

思路： 遍历链表到到 left的位置 以left 上一个节点为头结点，接下来遍历节点，以头插法的方式插入头结点上（此时问题 又转换到而来 反转链表 I 的问题，不同的是并不是遍历到尾）

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
 ListNode *reverseBetween(ListNode *head, int left, int right) {
    if(head->next == nullptr)
        return head;
    ListNode *vHead = new ListNode(0);
    vHead ->next = head;
    ListNode *p  = vHead;
    ListNode *q  = vHead->next;
 //	第一次for 循环走到 定位到 left 的位置，p和q
    for (int i = 0; i < left-1; i++) {
      p = p->next;
      q = q->next;
    }
//  第二次 for 开始反转需要的节点     
    for (int i = 0; i < right - left; i++) {
      //保留下一个节点
      ListNode *temp = q->next;
      // 为下一个反转做好准备
      q->next = q->next->next;
     //  头插法，查到  p 的后面
      temp->next = p->next;
      // 更新 p的位置 ，为 p做好准备
      p->next = temp;
    }
    return vHead->next;
  }

image-20220326152225259

K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

image-20220407144530921

思路： 每k个节点反转， 可以把问题拆分到 每组 k个节点的反转，最后将每组拼接起来，对于反转 一个链表比较容易，这次反转有指定得的范围，k个几点

​ 利用递归可以将每组拼接起来

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
class Solution {
public:
    //反转 k个节点的链表
    ListNode* reverseList(ListNode* head,ListNode* tail) {
     ListNode *vhead = new ListNode();
     ListNode *v = vhead->next;
     while(head != tail){
        ListNode *t = head->next;
        head->next = v;
        v = head;
        head = t; 
     }
     return v;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *node = head;
        //遍历k个节点
        for(int i = 0;i < k; i++){
            if(node == nullptr)
                return head;
            node = node->next;
        }
        //  传入首尾节点
        ListNode *res = reverseList(head,node);
        //  递归  此时head已经是尾节点
        head->next =reverseKGroup(node,k);
        return res;
    }
};