java单链表使用
孙霸天 人气:0链表的概念:
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点(链表中的每一个元素称为节点)组成,节点可以在运行时动态生成。每个节点包含两个部分:一个是存储数据元素的数据域,另一个是存储下一个节点地址的指针域。相对于线性表顺序结构,操作复杂。由于不必按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表的优势
不需要知道数据的大小,可以充分利用计算机内存空间,实现灵活的内存动态管理
链表允许插入和移除表上任意位置上的节点(但是不允许随机存取)
链表的缺点
不能像数组一样随机读取
增加了空间的开销(增加了节点的指针域)
代码实现
定义一个节点类
public class ListNode {//定义节点类 int val; ListNode next; ListNode(int x) { val = x; } //将数组的值赋给链表 public ListNode getList(int[] sums) { ListNode dummyHead = new ListNode(0); ListNode curr = dummyHead; for (int i = 0; i < sums.length; i++) { curr.next = new ListNode(sums[i]); curr = curr.next; } return dummyHead.next; } //将链表的值赋给list并打印 public void showList(ListNode listNode) { List list = new ArrayList(); while (listNode != null) { list.add(listNode.val); listNode = listNode.next; } for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } } /** * leetcode第二题 * * 给出两个非空的链表用来表示两个非负的整数, * 其中,它们各自的位数是按照逆序的方式存储的, * 并且它们的每一个节点只能存储一位数组。 * @param l1 * @param l2 * @return */ public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; } }
测试方法
public class main { public static void main(String[] args) { int a[] = {2, 4, 3}; int b[] = {5, 6, 4}; ListNode curr=new ListNode(0); ListNode l1=curr.getList(a); // curr.showList(l1); ListNode l2=curr.getList(b); // curr.showList(l2); ListNode l3=curr.addTwoNumbers(l1,l2); curr.showList(l3); } }
输入[2,4,3],[5,6,4]
输出[7,0,8]
加载全部内容