单链表

单链表的问题有许多巧妙的思想，只能多多积累。

头结点

头结点可以简化边界处理情况。

1. 创造链表时，通过头结点创建
2. 删除节点时，通过头结点删除

合并

01 21. 合并两个有序链表

02 23. 合并 K 个升序链表

拆分

01 86. 分隔链表

快慢指针

链表倒数第k个结点

倒数第k = 正数 n - k

先将 p1 走 k。
那么 p1 到 末尾 = n - k。

ListNode* kFromBottom(ListNode* head, int k) {
 
        ListNode* p1 = head, *p2 = head;

        for(int i = 0; i < k; i++)
            p1 = p1->next;

        while(p1){	//p1会走到空结点
            p1 = p1->next;
            p2 = p2->next;
        }
		return p2;
    }

链表是否成环

如果有环，则快指针 一定会遇到 慢指针

bool isCycle(ListNode* head) {
        
        ListNode* p1 = head, *p2 = head;

        while(p1 && p1->next){

            p1 = p1->next->next;
            p2 = p2->next;

            if(p1 == p2)
                return true;
            
                
        }

        return false;
    }

链表的中间结点

快指针以2倍速走

ListNode* middleNode(ListNode* head) {

        ListNode* p1 = head, *p2 = head;

        while(p1 && p1->next){

            p1 = p1->next->next;

            p2 = p2->next;
        }

        return p2;
    }

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

02 142. 环形链表 II

03 876. 链表的中间结点

相交

01 160. 相交链表

反转

反转链表

1. 递归

ListNode* reverseList(ListNode* head) {

        if(!head)
            return nullptr;

        if(!head->next)
            return head;

        ListNode* newHead = reverseList(head->next);

        head->next->next = head;

        //断开head
        head->next = nullptr;

        return newHead;
    }

2. 迭代
   

ListNode* reverseList(ListNode* head) {
        
        ListNode* last = nullptr;
        ListNode* p = head;
        
        while (p) {
            ListNode* next = p->next;

            p->next = last; //p->next指向 前一个节点
            last = p;
            
            p = next;
        }

        return last;
    }

反转前 N 个节点

ListNode* successor = nullptr; 

ListNode* reverseListN(ListNode* head, int n) {

        if(n == 1){
			successor = head->next;//使用递归，可以方便的记录后继结点
			return head;
		}

        ListNode* newHead = reverseListN(head->next, n - 1);

        head->next->next = head;

        //断开head
        head->next = successor;

        return newHead;
    }

反转任意区间

ListNode* reverseBetween(ListNode* head, int left, int right) {
	
	if(left == 1)
		return reverseListN(head, 1, right);
	
	head->next = reverseListN(head->next, left - 1, right - 1);
	
	return head;
}

01 206. 反转链表

02 92. 反转链表 II

03 25. K 个一组翻转链表