单链表操作

发表于 | 分类于
字数统计: 398

题目求两个链表都含有十进制数，相加，返回求和结果

​ 1->2->3->4

​ + 4->5

= 1->2->7->9

正好借这道题来总结一下单链表的操作

题解：这道题可以将两个链表逆序按位相加，链表节点为空则补0；注意进位的解决，最后得到的链表在逆序即为结果。

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

/**
 * Created by 90684 on 2018/6/15.
 */
// 定义链表节点结构体
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

// 将数字逆序存进链表，之后相加，得到的链表也是逆序存放的数
public class Leetcode_2 {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode prev = new ListNode(0);
        ListNode head = prev;
        int carry = 0; // 进位符
        while (l1 != null || l2 != null || carry != 0) {
            ListNode cur = new ListNode(0);
            int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
            cur.val = sum % 10;
            carry = sum / 10;
            prev.next = cur;
            prev = cur;
            l1 = (l1 == null) ? l1 : l1.next;
            l2 = (l2 == null) ? l2 : l2.next;
        }
        return head.next;
    }

    //将链表逆序  设置两个指针 一个 prev 一个 next
    public static ListNode reverse(ListNode l1) {
        ListNode prev = null;
        ListNode next;
        while (l1 != null) {
            next = l1.next;
            l1.next = prev;
            prev = l1;
            l1 = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        ListNode t1 = reverse(l1);
        ListNode b1 = new ListNode(4);
        ListNode b2 = new ListNode(5);
        b1.next = b2;   // 测试 可见链表相等可以继承此节点及之后的next所有的指针。
        ListNode b3 = reverse(b1); 
        ListNode result = reverse(addTwoNumbers(t1, b3));
        while (result != null) {
            System.out.print(result.val);
            result = result.next;
        }
        System.out.println();
    }
}
-------------The End-------------