提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

两个链表生成相加链表

2023-02-18 16:35:14 时间

题目：

 

 

 

思路：

本题难点：第一，不知道链条有多大，最合起来的数可能会远大于long与int能存的极限。
思路一，将链表反转，链条反转的链表从个位数开始相加，然后取余数，不断叠成新的链表。
思路二，将链表的数据取出组合成字符串，然后利用大数相加的方法，取得相加的和，然后根据新的和的字符串生成新的链表。（但实际上运算量有点过大，没有过测试）
 

代码示例：

public class Solution4 {
    public static void main(String[] args) {
        ListNode head = new ListNode(6);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(9);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(7);
        head.next = node2;
        node3.next = node4;
        node4.next = node5;
        ListNode result = addInList(head, node3);
        System.out.println(result);
        OutPutLinkedList(result);
    }
 
    /**
     * 方案2，采用合成字符串的形式
     * 但是这种方式运算效率太低了
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public static ListNode addInList(ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null)
            return head2;
 
        if (head2 == null)
            return head1;
 
        ListNode temp1 = head1, temp2 = head2;
        String str1 = "", str2 = "";
        while (temp1 != null) {
            str1 = str1 + temp1.val;
            temp1 = temp1.next;
        }
 
        while (temp2 != null) {
            str2 = str2 + temp2.val;
            temp2 = temp2.next;
        }
        String temp = solve(str1, str2);
        //构建头结点
        ListNode head = new ListNode(temp.charAt(0) - '0');
        ListNode result = head;
        for (int i = 1; i < temp.length(); i++) {
            ListNode tempNode = new ListNode((int) temp.charAt(i) - '0');
            head.next = tempNode;
            head = tempNode;
        }
        return result;
    }
 
    public static String solve(String s, String t) {
        StringBuilder ans = new StringBuilder();
        int tmp = 0;
        int ls = s.length() - 1, lt = t.length() - 1;
        while (ls >= 0 || lt >= 0 || tmp == 1) {
            int l = ls >= 0 ? (s.charAt(ls--) - '0') : 0;
            int r = lt >= 0 ? (t.charAt(lt--) - '0') : 0;
            int plus = l + r + tmp;
            tmp = plus / 10;
            char a = (char) (plus % 10 + '0');
            ans.append(a);
        }
        return ans.reverse().toString();
    }
 
    /**
     * 方案1，采用反转链表的形式
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public static ListNode addInList1(ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null)
            return head2;
 
        if (head2 == null)
            return head1;
 
        int num, num1, num2;
        //颠倒两个链条
        ListNode temp1 = reverseIteratively(head1);
        ListNode temp2 = reverseIteratively(head2);
        //构建头结点
        num = temp1.val + temp2.val;
        temp1 = temp1.next;
        temp2 = temp2.next;
        ListNode head = new ListNode(num % 10);
        num /= 10;
        //利用遍历产生链条
        while (temp1 != null || temp2 != null || num != 0) {
            num1 = 0;
            num2 = 0;
            if (temp1 != null) {
                num1 = temp1.val;
                temp1 = temp1.next;
            }
 
            if (temp2 != null) {
                num2 = temp2.val;
                temp2 = temp2.next;
            }
            num = num + num1 + num2;
            ListNode temp = new ListNode(num % 10);
 
            temp.next = head;
            head = temp;
            num /= 10;
        }
 
        return head;
    }
 
    public static ListNode reverseIteratively(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
 
 
    /**
     * 打印链表，用于输出查看
     *
     * @param head
     */
    public static void OutPutLinkedList(ListNode head) {
        ListNode temp = head;
        while (null != temp) {
            System.out.print(temp.val);
            if (null != temp.next) {
                System.out.print(" -> ");
            }
            temp = temp.next;
        }
        System.out.println();
    }
}
 
class ListNode {
    int val;
    ListNode next;
 
    ListNode() {
    }
 
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 

相关文章