leetcode82_删除排序链表中的重复元素2_快慢指针+递归

一. 链表的解法有两种常见的,一个是递归写法,一个是非递归写法.

二. 首先展示一下递归写法,递归写法的关键是明确函数的作用,然后假设此函数已经实现了这个功能,去推断下一个状态是怎么样的.

1. 本题中deleteDuplicates函数的作用是返回已经删除链表中重复元素的头指针.假设这个函数可以完成功能.

struct ListNode {
	int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode* deleteDuplicates(ListNode* head) {
		//递归终止条件,考虑最简单基础情况.
		if (head == NULL || head->next == NULL)
			return head;
		//递归,只需要分析前面的部分,举例,假设后面的功能已经完成.
		if (head != NULL&&head->next != NULL&&head->val == head->next->val) {
			while (head != NULL&&head->next != NULL&&head->val == head->next->val) {
				head = head->next;
			}
			head = deleteDuplicates(head->next);
		}
		else {
			head->next = deleteDuplicates(head->next);
		}
		return head;
	}
};


class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL || head->next==NULL) return head;
        if(head->val==head->next->val) {
            while(head!=NULL && head->next!=NULL && head->val==head->next->val)
                head = head->next;
            head = deleteDuplicates(head->next);
        }
        else head->next = deleteDuplicates(head->next);
        return head;
    }
};

三. 然后展示非递归写法,最好能画个图,理清逻辑.

1. 使用快慢指针,用快指针跳过那些有重复数组,慢指针负责和快指针拼接.

2. 思路可以借鉴递归的思路去思考.

struct ListNode {
	int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

//非递归写法
class Solution {
public:
	ListNode* deleteDuplicates(ListNode* head) {
		//边界条件
		if (head == NULL || head->next == NULL)
			return head;
		//定义一个哑变量,减少边界条件的判断.比如11123这种.
		ListNode* dummy = new ListNode(0);
		dummy->next = head;
		//定义快慢指针
		ListNode* slow = dummy;
		ListNode* fast = head;
		while (fast != NULL) {
			//如果当前值等于下一个.
			if (fast->next != NULL&&fast->val == fast->next->val) {
				int tmp = fast->val;
				//fast指针指向重复元素的下一个,借鉴了递归的思路.
				while (fast != NULL&&tmp == fast->val)
					fast = fast->next;
			}
			else {
				//借鉴递归思路,slow指向重复元素的下一个.
				slow->next = fast;
				slow = fast;
				fast = fast->next;
			}
		}
		//如果是1,2,2或者1,1这种例子,需要将slow的下一个指向NULL.
		slow->next = fast;
		return dummy->next;
	}
};