力扣-数据结构-5【算法学习day.76】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.奇偶链表

题目链接:328. 奇偶链表 - 力扣（LeetCode）

题面:

分析:构造两个虚拟头结点，分别表示奇数位置和偶数位置的头结点，然后维护一个指针遍历链表，指针所指向的是奇数位置的节点，指针的下一个位置就是偶数，然后就是链表的插入了

代码:

/**
 * 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 oddEvenList(ListNode head) {
        ListNode jhead = new ListNode();
        ListNode ohead = new ListNode();
        ListNode jnode = head;
        ListNode jpre = jhead;
        ListNode opre = ohead;
        while(jnode!=null){
           jpre.next = jnode;
           jpre = jnode;
           opre.next = jnode.next;
           opre = jnode.next;
           if(jnode.next==null)break;
           jnode = jnode.next.next;
        }
        jpre.next = ohead.next;
        return jhead.next;
    }
}

2.分隔链表

题目链接:86. 分隔链表 - 力扣（LeetCode） 

题面:

分析:这题同上一题，也可以维护两个虚拟头结点，然后遍历链表，最后两链表合并

代码:

/**
 * 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 partition(ListNode head, int x) {
        ListNode lhead = new ListNode();
        ListNode rhead = new ListNode();
        ListNode lpre = lhead;
        ListNode rpre = rhead;
        for(ListNode i = head;i!=null;i=i.next){
            if(i.val<x){
                lpre.next = i;
                lpre = i;
            }else{
                rpre.next = i;
                rpre = i;
            }
        }
        lpre.next = rhead.next;
        rpre.next = null;
        return lhead.next;
    }
}

3.两数相加II

题目链接:445. 两数相加 II - 力扣（LeetCode）

分析:这里的思路是双链表分别反转后便于计算并构建新的链表，然后反转后的头结点便是答案

代码:

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l1head = reverseLinks(l1);
        ListNode l2head = reverseLinks(l2);
        int jin = 0;
        ListNode fanahead = new ListNode();
        ListNode pre = fanahead;
        for(ListNode i = l1head,j = l2head;i!=null||j!=null;){
            int flag = 0;
            if(i!=null)flag+=i.val;
            if(j!=null)flag+=j.val;
            flag+=jin;
            ListNode node = new ListNode(flag%10);
            pre.next = node;
            pre = node;
            jin = flag/10;
            if(i!=null) i = i.next;
            if(j!=null) j = j.next;
        }
        if(0!=jin){
           ListNode node = new ListNode(jin);
           pre.next = node;
           pre = node;
        }
        
        return reverseLinks(fanahead.next);

    }
    public ListNode reverseLinks(ListNode head){
        ListNode pre = null;
        ListNode fhead = null;
        for(ListNode i = head;i!=null;){
            ListNode node = i.next;
            i.next = pre;
            pre = i;
            if(node==null){
                fhead = i;
                break;
            }
            i = node;
        }
        return fhead;
    }
}

 后言

上面是数据结构相关的习题，下一篇文章会将其他相关的习题。