有趣的两位数和单链表处理——Java解法

有趣的两位数

有数学家发现⼀些两位数很有意思，⽐如， 34 * 86 = 43 * 68 也就是说，如果把他们的十位数和个位数交换，二者乘积不变。编程求出满足该性质的两位数组合。提示，暴力解法非最优解。

解题思路

先给出暴力求解的答案。考虑到11X99=99X11，这种情况不属于解题集。另外，12X24=21X42和21X42=12X24这种情况看作一个解。

代码逻辑实现

import java.util.HashSet;
import java.util.Set;

public class swap {
    public static void main(String[] args) {
        fun();
    }
    public static void fun() {
        Set<String> set=new HashSet<>();
        int sum = 0;
        for (int i = 10; i <= 99; i++) {
            for (int j = i + 1; j <= 99; j++) {
                //排除两个数相等的情况，排除交换后还是自身的情况如12X21=21X12
                //排除十位和个位相等的情况，如11X22=11X22
                //排除重复的结果，如12X42=21X24和21X24=12X42
                if (i != j && Math.abs(j - i) % 9!=0 && i % 11 != 0 && j % 11 != 0 && i * j == trans(i) * trans(j)&&!set.contains(i+""+j)) {
                    sum++;
                    set.add(i+""+j);
                    set.add(trans(i)+""+trans(j));
                    System.out.println(i + "X" + j + "=" + trans(i) + "X" + trans(j));
                }
            }
        }
        System.out.println("总数为:" + sum);
    }

    public static int trans(int cur) {
        int units = cur % 10;
        int tens = cur / 10;
        return units * 10 + tens;
    }
}

/**
12X42=21X24
12X63=21X36
13X62=31X26
13X93=31X39
14X82=41X28
23X64=32X46
23X96=32X69
24X63=42X36
24X84=42X48
26X31=62X13
26X93=62X39
28X41=82X14
34X86=43X68
36X42=63X24
36X84=63X48
39X62=93X26
46X96=64X69
48X63=84X36
总数为:18
* /

单链表处理

假设线性表 L = {A1, A2, A3, A4, …, An-2, An-1, An}，采⽤带头节点的单链表保存。链接节点定义如下：

 typedef struct node {
   int data;
   struct node * next; 
 } NODE;

请设计⼀个算法，编程实现，重新排列 L 中的各节点，得到线性表 L’ = {A1, An, A2, An-1, A3, An2, … }。

解题思路

如果把这个问题的单链表换成数组，那问题就很简单了。考虑到单链表是单向的，因此我采用一个集合保存所有的单链表节点。然后让集合的前半部分元素和后半部分元素依次连接。

代码逻辑实现

import java.util.ArrayList;
import java.util.List;

public class SingleLinkedList {
    static class Node {
        Node next;
        int data;
        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        print(node1);
        arrange(node1);
        print(node1);
    }
    /**
     * 从head遍历打印出整个单链表
     * @param head 头结点
     */
    public static void print(Node head) {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    
    /**
     * 重新排列单链表
     * @param head 头结点
     */
    public static Node arrange(Node head) {
        List<Node> nodeList = new ArrayList<>();
        //存储所有节点
        while (head != null) {
            nodeList.add(head);
            head = head.next;
        }
        Node cur = null;
        //因为本质上类似交换数组首尾元素，因此只需要遍历1/2的数据就可以
        for (int i = 0; i < nodeList.size() / 2; i++) {
            //如果是第一个元素则当前节点为i所在节点
            //如果不是第一个元素，当前节点此时为上一次操作的最后一个元素
            //此时需要把当前节点指向i所在节点
            if (cur == null) {
                cur = nodeList.get(i);
            } else {
                cur.next = nodeList.get(i);
                cur = nodeList.get(i);
            }
            //获取列表另一半对应的结点
            Node last = nodeList.get(nodeList.size() - i - 1);
            if (last != null) {
                cur.next = last;
                //每次把last的指向设置为空
                last.next = null;
            }
            //将操作的后一半节点设置为当前节点
            cur = last;
            //如果单链表的个数为奇数，则在最后一次遍历的时候把最后一个节点指向中间节点
            if (i == nodeList.size() / 2 - 1 && nodeList.size() % 2 != 0 && cur != null) {
                Node middle = nodeList.get(nodeList.size() / 2);
                cur.next = middle;
                middle.next = null;
            }
        }
        return nodeList.get(0);
    }
}

/**
 *  原链表：1 2 3 4 5 6 7 
 *  重排后：1 7 2 6 3 5 4 
 */