链表的创建和使用
1，创建一个链表：
a,定义一个class类 ListNode 如下：
//创建一个链表的类
class ListNode{
int val; //数值 data
ListNode next; // 结点 node
ListNode(int x){ //可以定义一个有参构造方法，也可以定义一个无参构造方法
val = x;
}
// 添加新的结点
public void add(int newval) {
ListNode newNode = new ListNode(newval);
if(this.next == null)
this.next = newNode;
else
this.next.add(newval);
}
// 打印链表
public void print() {
System.out.print(this.val);
if(this.next != null)
{
System.out.print("-->");
this.next.print();
}
}
}
b,定义ListNode 类之后，我们开始插入结点，然后将链表打印出来
public class CreateListNode
{
public static void main(String[] args)
{
ListNode l1 = new ListNode(1); //创建链表对象 l1 （对应有参 和 无参 构造方法）
l1.add(2); //插入结点，打印
l1.add(3);
l1.print();
}
}
2,链表的实际应用：合并两个有序链表
题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
题目分析：
创建一个新链表：
给出两个指定链表，创建一个新的链表用来保存排序后的结果
排序：
对于排序，采用归并排序的方法，进行逐个交替插入
剩余插入：
如果有一个为空的话(本来就为空；插入时先插完为空)，将剩余链表内容直接链到新链表上
代码展示(已验证):
//leetcode-java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
//c语言代码
// if(l1 == NULL)
// return l2;
// if(l2 == NULL)
// return l1;
// if(l1.val < l2.val)
// {
// l1.next = mergeTwoLists(l1.next,l2);
// return l1;
// }
// else
// {
// l2.next = mergeTwoLists(l1,l2.next);
// return l2;
// }
ListNode dummyHead = new ListNode(0);//创建一个新链表， dummyHead 虚拟头结点
ListNode curr = dummyHead;
while(l1 != null && l2 != null)
{ if(l1.val < l2.val)
{
curr.next = l1;
curr = curr.next;
l1 = l1.next;
}
else
{
curr.next = l2;
curr = curr.next;
l2 = l2.next;
}
}
// 有一方为空时，直接将剩下的链接到 curr 上
if(l1 == null)
curr.next = l2;
else
curr.next = l1;
return dummyHead.next; // 从头结点之后开始返回，也就是合并之后的链表
}
}
泡泡：
这一类的链表的问题还有很多，像：
合并链表并删除其中某个元素，
合并链表并且对应位置相加保持进位
......
还有很多需要学习的东西，0.0