删除已排序链表中重复的元素，使得每个元素只出现一次

例如输入：1 -> 2 -> 2 -> 3

输出：1 ->2 -> 3
算法思路：

表中并没有说明带有头结点，设头指针L，首结点p（指针为L）
遍历整个表，进入循环体：拿当前结点与后继结点进行对比，如果二者相同，直接删除这个后继结点，这样使得每个元素只出现一次；
如果二者不相同，把当前指针p顺序后移；

void delete_duplicates(LinkList &L){
	ListNode* p =L;
	ListNode* q;
	/*这里解释下循环的限制:当链表不为空，
	并且当前不为尾节点（最大为尾节点的前驱结点，当此时为尾节点的前驱时，
	直接将当前结点p置为尾节点，因为此时p->next=NULL*/		
	while (p != NULL && p->next != NULL){
		if (p->data == p->next->data){
			q = p->next;		//用于释放内存空间
			p->next = p->next->next;
			free(q);
		}else{
			p = p->next;
			}
	}
}		

实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。

给定待删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true

直接free(p)，这样行不通，因为我们不能访问其他结点；

如果我们只能访问该结点，可以尝试将该结点的后继结点的数据复制到当前结点，然后删除后继结点

typedef struct  SListNode {
    int  value;    // 保存的值
    struct SListNode* next;    // 保存下一个结点的地址
} SListNode_t;


bool deleteNode (SListNode_t *node) {
	if( NULL == node || NULL == node->next ) 
    {
        return false;
    }   
	SListNode_t * next = node->next;
	node->value = next->value;
	node->next = next->next;
	return true;
}


 

直接free(p)，这样行不通，因为我们不能访问其他结点；
如果我们只能访问该结点，可以尝试将该结点的后继结点的数据复制到当前结点，然后删除后继结点
public static boolean deleteNode (LinkListNode n) {
	if( null == n || null == n.next ) return false;
	LinkListNode next = n.next;
	n.data = next.data;
	n.next = next.next;
	return true;
}


但是这样做有一个问题，如果我们要删除的是尾结点，这个算法就失效了，如果是尾结点，可以考虑将这个结点置为fake吗？

已知L 是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点

1.删除P结点的直接后继结点

思路：先用工作结点保存P结点的直接后继，然后将P结点的指针域指向P结点的直接后继节点的直接后继节点，然后再删除该工作结点。



Q = P->next;

P->next = P->next->next;

free(Q);

2.删除P节点的直接前驱结点（有毛病）

思路：用工作结点保存P结点，然后将表头结点赋给P结点，进行遍历，找到初始时P结点的直接前驱结点的直接前驱结点，即为此时的P结点，再将该P结点的指针域指向其直接后继结点的直接后继结点，即指向初始时的P结点

Q = P;

P = L;

while (P->next->next != Q) {

    P = P->next;

}

P->next = P->next->next;

free(Q);

 

3.删除P结点（有毛病）

 

Q = P;

P = L;

while (P->next != Q) {

    P = P->next;

}

P->next = P->next->next;

free(Q);

 

4.删除首元结点



P = L;

Q = P->next;

P->next = P->next->next;

free(Q);

 

5.删除尾元结点

 

while(P->next->next != NULL) {//找到尾元结点的直接前驱结点

    P = P->next;

}

//P结点即为尾元结点的直接前驱，Q结点即为尾元结点

Q  = P->next;

P->next = P->next->next;//尾元结点的指针域实际是指向空

free(Q);