算法练中将包含相关算法和一些与考研题目结合的C语言的算法题进行延伸思考，在用Java简单实现的同时，对内容深化并尝试C语言的叙述来更加巩固当前知识点。

题目1

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。

示例图

方法：一次遍历

思路

这个题的思路比较简单，因为是按升序排列的，所以重复的元素基本都是相邻着的，因此只需要比较相邻两个节点的值，就能判断出是否是重复的。

代码实现

//删除链表中的重复元素
public class test {
    public static void main(String[] args) {

        Node head = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(1);
        Node node3 = new Node(3);
        Node node4 = new Node(3);
        Node node5 = new Node(5);

        head.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);

        Node h = head;
        while (h != null){
            System.out.print(h.getData() + "");
            h = h.getNext();
        }
        Solution solution = new Solution();
        head = solution.deleteDuplicates(head);

        System.out.print("\n**********************");
        // 打印删除重复元素后的链表
        while (head != null){
            System.out.println(head.getData() + "");
            head = head.getNext();
        }
    }
}

class Solution{
    //算法主体
    public Node deleteDuplicates(Node head) {
        if (head ==null ){
            return head;
        }
        Node cur = head;
        while (cur.getNext() != null){
            //比较相邻两节点的值，若相等，就让cur的next指向下下个节点
            if(cur.getData() == cur.getNext().getData()){
                cur.setNext(cur.getNext().getNext());
            }
            else {
                cur = cur.getNext();    //若相邻不相等，就让cur往后移一位
            }
        }
        return head;
    }
}

//构造节点类
class Node{
    private int Data;   //数据域
    private Node next;  //指针域

    public Node(int Data){
        this.Data = Data;
    }

    public int getData(){
        return Data;
    }

    public void setData(int Data){

        this.Data = Data;
    }

    public Node getNext(){

        return next;
    }

    public void setNext(Node next){

        this.next = next;
    }
}

输出结果：

011335
0135

算法主体

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head ==null ){
            return head;
        }
            ListNode cur = head;
            while(cur.next !=null ){
                if(cur.val == cur.next.val ){
                    cur.next = cur.next.next;
                }
                else {
                    cur = cur.next;
                }
            }
        return head;
    }
}

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (!head) {
        return head;
    }

    struct ListNode* cur = head;
    while (cur->next) {
        if (cur->val == cur->next->val) {
            cur->next = cur->next->next;
        } else {
            cur = cur->next;
        }
    }

    return head;
}

复杂度

时间复杂度：O(N)，N是链表长度

空间复杂度：O(1)

扩展延伸

题目2

思路

算法的基本设计思想

算法的核心思想是用空间来换时间。使用辅助数组来记录链表中已经出现的数值，这样只用对链表进行一次遍历
因为|data|<=0，所以辅助数组q的大小为n+1，让各个元素的初始值置为0，如果在遍历链表过程中首次出现|data|，就令这个q[|data|]为1，这样后面如果出现了第二次|data|，就可以把它从链表中删除。

用C语言描述单链表节点的数据类型定义

typedef struct node{
  int data;
  struct node *link;
}NODE;
Typedef NODE *PNODE;

算法实现

void func (PNODE h, int n)
{
  PNODE p=h, r;
  int *q, m;
  q= (int *)malloc(sizeof(int)*(n+1));   //申请n+1个位置的辅助空间
  for(int i=0;i<n+1;i++)
    *(q+i) = 0;													//将数组元素的初始值置为0
  while(p->link != null)
  {
    m=p->link->data>0? p->link->data : -p->link->data;  //判断正负，将条件全部变成绝对值
    if(*(q+m) == 0)				//判断此时该结点data是否出现过
    {
      *(q+m) = 1;   			//首次出现，赋值1进行标记
      p= p->link;   			//保留
    }
    else   								//重复出现
    {
      //删除该结点
      r= p->link;
      p->link = r->link;
      free(r);
    }
  }
  free(q);
}