LeetCode 链表[L1]

面试题18. 删除链表的节点

写法一：
因为有可能会删掉链表的head节点，为了避免讨论这种情况，引入一个头节点(-1)，解决链表题目的常规操作了。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode *p=new ListNode(-1);
        ListNode *cur=p;
        p->next=head;
        while(cur->next!=NULL)
        {
            if(cur->next->val==val)
            {
                cur->next=cur->next->next;
                deleteNode(cur->next,val);
                break;
            }
            cur=cur->next;
        }
        return p->next;
    }
};

写法二：
cur用于探测，让探测的先走

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode *pre=nullptr;
        ListNode *cur=head;
        while(cur&&cur->val!=val)
        {
            pre=cur;
            cur=cur->next;
        }
        if(cur==head) return cur->next;
        pre->next=cur->next;
        return head;
    }
};

876. 链表的中间结点

• 方法：快慢指针法

当用慢指针 slow 遍历列表时，让另一个指针 fast 的速度是它的两倍。
当 fast 到达列表的末尾时，slow 必然位于中间。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

时间复杂度：
O(N)。

空间复杂度：
O(1)，slow 和 fast 用去的空间。

---

206.反转链表

不画图真的挺抽象的

• 算法1 (链表操作，迭代) O(n)

翻转:将所有节点的next指针指向前驱节点。
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。

空间复杂度：
遍历时只有3个额外变量，所以额外的空间复杂度是 O(1)。

时间复杂度：
O(n)。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr;
        ListNode *cur=head;
        while(cur)
        {
            ListNode *next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

• 算法2(链表操作，递归) O(n)

reverseList 函数它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail。

空间复杂度：
总共递归 n 层，系统栈的空间复杂度是 O(n)，所以总共需要额外 O(n) 的空间。

时间复杂度：
链表中每个节点只被遍历一次，所以时间复杂度是 O(n)。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      if(!head||!head->next) return head;
      ListNode *tail=reverseList(head->next);
      //找到尾巴后递归返回；
      head->next->next=head;
      head->next=nullptr;
      return tail
    }
};

---

相交链表

现代浪漫算法。。。。。

假设把两个链表长度合并，路程一样，速度一样，两个指针总会跑到一起。❤

具体的情况可以分析一下→

开始写的时候这样写，没有公共部分，就一直跑死循环了，所以我们设置最后一个NULL结点是为了保证让他俩一定能相遇

if(p1->next==NULL)
       p1=headB; 
else
       p1=p1->next;

空间复杂度： O(1)
时间复杂度为： O(n)

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB)  return NULL;
        ListNode *p1=headA,*p2=headB;
         while (p1 != p2) {
        p1 = p1 == NULL ? headB : p1->next;
        p2 = p2 == NULL ? headA : p2->next;
       }
        return p1;
    }
};