链表OJ题

简介: 链表OJ题

题目一:206反转链表

题目要求:

思路分析:两种思路

 

代码实现:

struct ListNode* reverseList(struct ListNode* head){
//n1,n2反转指针  n3链接下一个结点的指针
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    if(n2)//有可能head本身就是空指针
        n3 = n2->next;
    while(n2)//结束条件:n2==NULL
    {
        n2->next = n1;
        //反转链表
        n1 = n2;
        n2 = n3;
        if(n3)//坑2:n3到NULL之后要停止,因为不存在NULL->next
            n3 = n3->next;
    }
    return n1;
}
//第二种写法-->头插
struct ListNode* reverseList(struct ListNode* head){
    //设置新的头结点,进行头插
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    //头插
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

题目二:27.移除元素

题目要求:

思路分析:

代码实现:

int removeElement(int* nums, int numsSize, int val){
    int src = 0,dest = 0;
    while(src < numsSize)
    {
        //等于val,src++,相当于删除
        //不等于val,把src位置的值覆盖到dest位置,src++,dest++
        if(nums[src] != val)
        {
            nums[dest++]=nums[src++];
            // dest++;
            // src++:
        }
        else
        {
            src++;
        }
    }
    return dest;
}

题目三:删除有序数组中的重复项

题目要求:

思路分析:

代码实现:

int removeDuplicates(int* nums, int numsSize){
    int src = 0;
    int dest = 0;
    while(src < numsSize)
    {
        //相等src++
        if(nums[src] == nums[dest])
        {
            src++;
        }
        //不等-->将src赋给dest的下一个,src++,dest++
        else
        {
            nums[++dest] = nums[src++];
        }
    }
    return dest+1;
}

题目四:88.合并两个有序数组

题目要求:

思路分析:

代码实现:

//方法1
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1 = m - 1;//nums1末位
    int end2 = n - 1;//nums2末位
    int end = m + n - 1;//整个数组的末位
    while (end1 >= 0 && end2 >= 0)//循环条件:两个都没有结束
    {
        //倒着插入,取大的覆盖
        if (nums1[end1] > nums2[end2])
        {
            nums1[end--] = nums1[end1--];
        }
        else
        {
            nums1[end--] = nums2[end2--];
        }
    }
    //nums2有剩余,把剩余元素赋给nums1
    while (end2 >= 0)
    {
        nums1[end--] = nums2[end2--];
    }
}
//方法2
int cmp_int(const void* ptr1, const void* ptr2)
{
  return (*(int*)ptr1 - *(int*)ptr2);
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
  //第二种方法:存到一起,再利用qsort函数
  //直接强行合并两个数组
  int i = m;
  int j = 0;
  while (j < n)
  {
    nums1[i] = nums2[j];
    j++;
    i++;
  }
  //利用qsort函数排序
  qsort(nums1, m + n, 4, cmp_int);
}

总结:

1.一个思路“双指针法”,即利用移动指针(src)和目标指针(dest),来完成对数组元素的操作,大家可以多多画图去理解这个过程;

2.“三指针法”求反转链表,两个指针进行反转,一个指针保证链表的“连接性”

目录
相关文章
|
12月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
98 7
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
106 8
【数据结构OJ题】合并两个有序链表
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
131 1
【数据结构OJ题】复制带随机指针的链表
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
111 1
【数据结构OJ题】链表中倒数第k个结点
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
147 0
【数据结构OJ题】链表的回文结构