物联网项目 阿里巴巴 Jenkins cordova xaml cookies testng Pure CSS Egret Engine bootstrap后台管理系统模板 ppt视频教程下载 access教学视频 mysql倒序 安卓程序源代码 docker保存镜像 docker启动命令 网页设计公司 python当前日期 配置java开发环境 java接口实现 java8时间 java获取文件 java网页 h5模板 linux格式化命令 corelpainter 找茬辅助 cg模宝 rar去广告 三维看图软件 海妖花粉哪里多 dll下载 pr怎么放大视频画面 淘宝图片下载 js切割字符串 一键隐藏 ps出血 ps怎么做动画 机械键盘怎么关闭灯光 ibeacon定位
当前位置: 首页 > 学习教程  > 编程语言

数据结构 链表 算法问题总结

2020/7/24 10:22:32 文章标签:

数据结构 链表 算法问题总结

public static class  ListNode{
    int val;
    ListNode next;
    ListNode(int x)
    {
        val =x;
        next =null;
    }
}

一、找出两个链表的交点(结点)

Leetcode

例如以下示例中 A 和 B 两个链表相交于 c1:

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

1.while循环判断两链表下一结点是否相等,A链表走完走B链表,B链表走完走A链表,两者总长度相等,速度相同

2.循环退出的条件是两结点相等。

3.方法返回当前结点即为相交结点

 public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA ==null||headB==null)
    {
        return null;
    }
    ListNode you=headB;ListNode she=headA;

    while(you!=she)
    {
        you=you!=null?you.next:headA;
        she=she!=null?she.next:headB;
    }

    return you;
}

二、链表反转

Leetcode

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1.头插法

2.先保存下一结点信息,头结点的指向重新分配,头结点插入在新节点的指向,下一结点重新为头结点

3.循环结束条件头结点不为空

public static intersect.ListNode reverseList(intersect.ListNode head){
    intersect.ListNode newHead=new intersect.ListNode(-1);

    while(head!=null)
    {
        intersect.ListNode next=head.next; //临时保存下一结点
        head.next =newHead.next;  //重新分配头结点的链接信息
        newHead.next=head;  //插入头结点
        head=next;      //下一结点作为头结点
    }
    return  newHead.next;
}

三、归并两个有序链表

Leetcode

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

1.递归

2.逐结点比较,比较两结点的大小,改变结点的指向,递归

public static intersect.ListNode mergeTwoLists(intersect.ListNode l1, intersect.ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

四、从有序链表中删除重复节点

Leetcode

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

1.递归

2.改变结点的指向,递归

3.比较结点是否相等决定返回当前结点还是下一结点

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    return head.val == head.next.val ? head.next : head;
}

五、删除链表的倒数第 n 个节点

Leetcode

Given linked list: 1->2->3->4->5, and n = 2.
output 1->2->3->5.

1.快慢结点结合

2.快结点

3.比较结点是否相等决定返回当前结点还是下一结点

public ListNode removeNthFromEnd(ListNode head, int n) {

    //思想,快慢结点结合,慢的结点减去先走的快结点就是倒数第n位结点
 ListNode fast=head;
 while(n-->0)
 {
     fast=fast.next;
 }
 if (fast==null)
   return head.next;
   ListNode slow=head;
   while(fast!=null && fast.next !=null)
   {
       fast=fast.next;
       slow=slow.next;
   }

   slow.next=slow.next.next;
   return head;
}

六、交换链表中的相邻结点

Leetcode

Given 1->2->3->4, you should return the list as 2->1->4->3.

1.先保存下一结点的信息

2.相邻结点的第一个结点的指向为下下下个结点

3.相邻结点的第二个结点的指向为第一个结点

public static intersect.ListNode swapPairs(intersect.ListNode head) {

    intersect.ListNode newNode=new intersect.ListNode(-1);
    newNode.next=head;

    intersect.ListNode pre=newNode;
    while(pre.next!=null&&pre.next.next!=null)
    {
        intersect.ListNode l1=pre.next;
        intersect.ListNode l2=pre.next.next;
        intersect.ListNode next=l2.next; //取对结点的下一结点作为后继结点,
        l1.next=next;    //添加在前一结点的后面
        l2.next=l1;      //将前一结点放在对节点中后一个结点的后面


        pre.next=l2; //重新赋值继续
        pre=l1;
    }

    return newNode.next;
}

七、链表求和

Leetcode

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7

1.先用栈(先进后出)保存链表值的信息

2.出栈累加俩个栈顶的值,carry变量统计进位信息

3.细节,一个栈为空,另一个栈还有值时,给空栈赋值为0,对进位的元素取余作为当前结点的值,进位用carry变量保存。

public static intersect.ListNode addTwoNumbers(intersect.ListNode l1, intersect.ListNode l2) {
    Stack<Integer> l1Stack = buildStack(l1);
    Stack<Integer> l2Stack = buildStack(l2);
    intersect.ListNode head = new intersect.ListNode(-1);
    int carry = 0; //进位标志
    while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
        int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
        int y = l2Stack.isEmpty() ? 0 : l2Stack.pop(); //通过出入栈,进行累加元素
        int sum = x + y + carry;
        intersect.ListNode node = new intersect.ListNode(sum % 10);
        node.next = head.next;
        head.next = node; //头插法
        carry = sum / 10;
    }
    return head.next;
}

八、回文链表

Leetcode

输入: 1->2
输出: false

输入: 1->2->2->1
输出: true

1.设置快慢结点,快结点走的比慢结点快2倍,快结点走完时,慢结点的位置位于总长的一半。

2.我们按慢结点的位置对链表进行分割。

3.将后半部分反转,与前半部分进行值的比较。

/**
 * 快慢结点的遍历,可以获取相应的链表长度
 * @param head
 * @return
 */
public static boolean isPalindrome(intersect.ListNode head) { //暴力解法,获取一半的长度,头插法反转后半部分,与前半部分的值进行比较
    if (head == null || head.next == null) return true;
    intersect.ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;//快结点的速度是慢结点的2倍,当快结点跑完的时候,慢结点的位置就是一半的长度
    }
    if (fast != null) slow = slow.next;  // 偶数节点,让 slow 指向下一个节点
    cut(head, slow);                     // 切成两个链表
    return isEqual(head, reverse(slow));
}

/**
 * 根据结点分开链表
 * @param head
 * @param cutNode
 */
private static void cut(intersect.ListNode head, intersect.ListNode cutNode) {
    while (head.next != cutNode) {
        head = head.next;
    }
    head.next = null;
}

/**
 * 头插法,反转链表
 * @param head
 * @return
 */
private static intersect.ListNode reverse(intersect.ListNode head) {
    intersect.ListNode newHead = null;
    while (head != null) {
        intersect.ListNode nextNode = head.next;
        head.next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

九、分隔链表

Leetcode

Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

1.分割的原理就是按分割的个数,断去最后一个结点的指向。

2.统计链表的长度,统计多余的长度放置首链表数组

3.每一段的个数循环下移,够了之后断开指向

   public static intersect.ListNode[] splitListToParts(intersect.ListNode root, int k) {
        int N = 0;
        intersect.ListNode cur = root;
        while (cur != null) {
            N++;
            cur = cur.next;
        }
        int mod = N % k;
        int size = N / k;
        intersect.ListNode[] ret = new intersect.ListNode[k];
        cur = root;
        for (int i = 0; cur != null && i < k; i++) {
            ret[i] = cur;
            int curSize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < curSize - 1; j++) {
                cur = cur.next;   //下移
            }
            intersect.ListNode next = cur.next;
            cur.next = null;  //分割的原理是断链,断去指针的指向
            cur = next;
        }
        return ret;
    }

十、链表元素按奇偶聚集

Leetcode

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

1.改变结点的指向。

2.定义俩个头结点,奇元素的指向为当前元素的下下结点,偶元素(奇元素+1)的指向为下下结点

3.需要单独的保存一下偶结点的起始结点,为奇结点的最后一个结点的指向

public static intersect.ListNode oddEvenList(intersect.ListNode head) {
    if (head == null) {
        return head;
    }
    intersect.ListNode odd = head, even = head.next;
    intersect.ListNode evenHead = even; //保留偶数的起始点链表地址,因为even到后面会改变!

    while (even != null && even.next != null) {
        odd.next = odd.next.next;
        odd = odd.next;
        even.next = even.next.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

十一、思想总结

快慢结点,递归,头插法.


本文链接: http://www.dtmao.cc/news_show_50262.shtml

附件下载

上一篇:PTA 7-14 求整数段和

下一篇:vue 重新学习

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?