算法第六节

K个节点的组内逆序调整

给定一个单链表的头节点head，和一个正数k
实现k个节点的小组内部逆序，如果最后一组不够k个就不调整
例子:
调整前：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8，k = 3
调整后：3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8

public class demo17 {
    /**
     * 给定一个单链表的头节点head，和一个正数k
     * 实现k个节点的小组内部逆序，如果最后一组不够k个就不调整
     * 例子:
     * 调整前：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8，k = 3
     * 调整后：3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
     */
    public static class ListNode {
        public int value;
        public ListNode next;

        public  ListNode(int num) {
            value = num;
            next = null;
        }
    }


    public static void main(String[] args) {
        int num = (int) (Math.random() * 100)+1;
        System.out.println(num+"======");
        ListNode node=new ListNode(1);
        ListNode node1=node;
        for (int i = 0; i < num; i++) {
            node.next=new ListNode(i+2);
            node=node.next;
        }
        int lenth=((int) (Math.random() * 9)+3);
        System.out.println(lenth+"======");
        ListNode listNode = ReverseNodesInKGroup(node1,lenth);
        while (listNode!=null){
            System.out.println(listNode.value);
            listNode=listNode.next;
        }
    }

    public static ListNode lastNode(ListNode node,int k) {
        while(--k>0&&node!=null){
            node=node.next;
        }
        return node;
    }

    public static void reverNode(ListNode start,ListNode end) {
        end=end.next;
        ListNode pre=null;
        ListNode next=null;
        ListNode cur=start;
        while (cur!=end){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        start.next = end;
    }

    public static ListNode ReverseNodesInKGroup(ListNode node,int lenth) {
        ListNode start=node;
        ListNode lastnode = lastNode(node,lenth);
        if(lastnode==null){
            return node;
        }
        node=lastnode;
        reverNode(start,lastnode);
        ListNode lastEnd = start;
        while (lastEnd.next!=null){
            start=lastEnd.next;
            lastnode = lastNode(start,lenth);
            if(lastnode==null){
                return node;
            }
            reverNode(start,lastnode);
            lastEnd.next=lastnode;
            lastEnd = start;
        }
        return node;
    }

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

两个链表相加

给定两个链表的头节点head1和head2，
认为从左到右是某个数字从低位到高位，返回相加之后的链表
例子 4 -> 3 -> 6 2 -> 5 -> 3
返回 6 -> 8 -> 9
解释 634 + 352 = 986

public class demo18 {
    /**
     * 给定两个链表的头节点head1和head2，
     * 认为从左到右是某个数字从低位到高位，返回相加之后的链表
     * 例子     4 -> 3 -> 6        2 -> 5 -> 3
     * 返回     6 -> 8 -> 9
     * 解释     634 + 352 = 986
     */
    public static class ListNode {
        public int value;
        public ListNode next;

        public ListNode(int num) {
            value = num;
            next = null;
        }
    }

    public static void main(String[] args) {
        int num = (int) (Math.random() * 9)+1;
        ListNode node = new ListNode(num);
        System.out.print(num+ " ");
        ListNode node1 = node;
        for (int i = 0; i < num; i++) {
            int num1 = (int) (Math.random() * 10);
            System.out.print(num1+ " ");
            node.next = new ListNode(num1);
            node = node.next;
        }
        System.out.println();
        int num2 = (int) (Math.random() * 9)+1;
        ListNode node2 = new ListNode(num2);
        System.out.print(num2+ " ");
        ListNode node3 = node2;
        for (int i = 0; i < num2; i++) {
            int num1 = (int) (Math.random() * 10);
//            int num1=9;
            System.out.print(num1+ " ");
            node2.next = new ListNode(num1);
            node2 = node2.next;
        }
        System.out.println();
        ListNode listNode = AddTwoNumbers(node1, node3);
        while (listNode != null) {
            System.out.print(listNode.value+ " ");
            listNode = listNode.next;
        }
    }

    public static int lenth(ListNode node){
        int num=0;
        while (node.next!=null){
            num++;
            node=node.next;
        }
        return num;
    }

    public static ListNode AddTwoNumbers(ListNode node1, ListNode node2) {
        int l1=lenth(node1);
        int l2=lenth(node2);
        ListNode lhead=l1>=l2?node1:node2;
        ListNode shead=lhead==node1?node2:node1;
        ListNode ans=lhead;
        int jinwei=0;
        ListNode last = lhead;
        while (shead!=null){
            int num=lhead.value+shead.value+jinwei;
            lhead.value=num%10;
            jinwei=num/10;
            last=lhead;
            lhead=lhead.next;
            shead=shead.next;
        }
        while (lhead!=null){
            int num=lhead.value+jinwei;
            lhead.value=num%10;
            jinwei=num/10;
            last=lhead;
            lhead=lhead.next;
        }
        if (jinwei!=0){
            last.next=new ListNode(1);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

两个有序链表的合并

给定两个有序链表的头节点head1和head2，
返回合并之后的大链表，要求依然有序
例子 1 -> 3 -> 3 -> 5 -> 7 2 -> 2 -> 3 -> 3-> 7
返回 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7

public class demo19 {
    /**
     * 两个有序链表的合并
     * 给定两个有序链表的头节点head1和head2，
     * 返回合并之后的大链表，要求依然有序
     * 例子     1 -> 3 -> 3 -> 5 -> 7          2 -> 2 -> 3 -> 3-> 7
     * 返回     1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7
     */
    public static class ListNode {
        public int value;
        public ListNode next;

        public  ListNode(int num) {
            value = num;
            next = null;
        }
    }

    public static void main(String[] args) {
        int num = (int) (Math.random() * 9)+1;
        ListNode node = new ListNode(num);
        System.out.print(num+ " ");
        ListNode node1 = node;
        for (int i = 1; i <=num; i++) {
            int num1 =i+num;
            System.out.print(num1+ " ");
            node.next = new ListNode(num1);
            node = node.next;
        }
        System.out.println();
        int num2 = (int) (Math.random() * 9)+1;
        ListNode node2 = new ListNode(num2);
        System.out.print(num2+ " ");
        ListNode node3 = node2;
        for (int i = 1; i <= num2; i++) {
            int num1 =i+num2;
            System.out.print(num1+ " ");
            node2.next = new ListNode(num1);
            node2 = node2.next;
        }
        System.out.println();
        ListNode listNode = mergeTwoLists(node1, node3);
        while (listNode != null) {
            System.out.print(listNode.value+ " ");
            listNode = listNode.next;
        }
    }

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        ListNode head=head1.value<=head2.value?head1:head2;
        ListNode cur1=head.next;
        ListNode cur2=head==head1?head2:head1;
        ListNode pre=head;
        while (cur1!=null&&cur2!=null){
            if(cur1.value>=cur2.value){
                pre.next=cur2;
                cur2=cur2.next;
            }else{
                pre.next=cur1;
                cur1=cur1.next;
            }
            pre=pre.next;
        }
        pre.next=cur1!=null?cur1:cur2;
        return head;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71