两个排序链表合并
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
有两种解法:
1、迭代
2、递归
需要注意的是,迭代是next赋值(a->next = l1),所以返回值也要next,
而递归是直接赋值(pNewHead = pHead1),所以返回头节点就可以了。
迭代方法
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(0); //ListNodelist=newListNode(0) 初始化一个节点值为0的空节点,最常用最正规写法; ListNode* a=head; while(l1 != nullptr && l2!=nullptr) { if(l1->val < l2->val){ a->next = l1; l1 = l1->next; }else{ a->next = l2; l2 = l2->next; } a = a->next; } if(l1==nullptr){ a->next = l2; }else{ a->next = l1; } return head->next; } };
递归方法
class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1 == nullptr) return pHead2; if(pHead2 == nullptr) return pHead1; ListNode* pNewHead = nullptr; if(pHead1 -> val < pHead2 -> val) { pNewHead = pHead1; pNewHead -> next = Merge(pHead1 -> next , pHead2); } else { pNewHead = pHead2; pNewHead -> next = Merge(pHead1 , pHead2 -> next); } return pNewHead; } };
删除排序链表中的重复元素
单指针
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(!head||!head->next) return head; ListNode* p=head; while(p->next!=NULL&&p!=NULL) { if(p->val == p->next->val) { p->next=p->next->next; } else p=p->next; } return head; } };
双指针
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head==NULL||head->next==NULL) return head; ListNode* p=head;//慢指针 ListNode* q=head->next;//快指针 while(p->next!=NULL) { if(p->val==q->val)//找到重复元素 { if(q->next==NULL)//快指针后面若没有元素直接剔除 p->next=NULL; else//快指针后有元素 { p->next=q->next; q=q->next; } } else //元素不相等 { p=p->next; q=q->next; } } return head; } };