技巧 - 链表操作

合并两个有序链表

• 148. 排序链表
• 25. K 个一组翻转链表
• 707. 设计链表
  • 使用二级指针来标记前驱节点的next地址

    ListNode* merge(ListNode* l, ListNode* r)
    {
    	ListNode* head = ((l->val <= r->val) ? l : r);
    	ListNode** prev_ptr = &head;
    	while(l && r)
    	{
    		if (l->val <= r->val)
    		{
    			*prev_ptr = l;
    			prev_ptr = &l->next;
    			l = l->next;
    		}
    		else
    		{
    			*prev_ptr = r;
    			prev_ptr = &r->next;
    			r = r->next;
    		}
    	}
    	while (l) {*prev_ptr = l; prev_ptr = &l->next; l = l->next;}
    	while (r) {*prev_ptr = r; prev_ptr = &r->next; r = r->next;}
    	/* return ptr of head !!! */
    	return head;
    }

获取下标为index的节点值

class MyLinkedList {

public:
	MyLinkedList() : count(0), head(nullptr) {}
	int get(int index);

private:
	LinkNode* head;
	size_t count;
}

int get(int index)
{
	int ret = -1;
	if (index < count)
	{
		LinkNode** prev_ptr = &head;
		for (int i = 0; i < index; ++i)
		{
			prev_ptr = &((*prev_ptr)->next);
		}
		/* *prev_ptr即：下标为index的节点指针 */
		ret = (*prev_ptr)->val;
	}
	
	return ret;
}