第一个问题：反转链表
1. 题目描述
输入一个链表，反转链表后，输出新链表的表头。
2. 解题思路
定义三个指针：
第一个指针指向当前正在处理的节点；
第二个指针指向当前处理节点的下一个节点，该指针是为了保证正常的遍历完顺序链表的所有节点；
第三个指针指向当前处理节点的上一个节点，这里主要是为了修改当前指针的指向，也就是指向反向；
3. 代码
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
public class ReverseList {
public static void main(String[] args) {
// 定义节点
ListNode root = new ListNode(0) ;
ListNode n1 = new ListNode(3) ;
ListNode n2 = new ListNode(5) ;
ListNode n3 = new ListNode(6) ;
ListNode n4 = new ListNode(7) ;
ListNode n5 = new ListNode(9) ;
// 连接节点
root.next=n1;
n1.next=n2;
n2.next=n3;
n3.next=n4;
n4.next=n5;
ListNode tmpnode=root;
while(tmpnode!=null) {
System.out.print(tmpnode.val);
tmpnode=tmpnode.next;
}
System.out.println();
ListNode nodenew= RevList(root);
while(nodenew!=null) {
System.out.print(nodenew.val);
nodenew=nodenew.next;
}
}
public static ListNode RevList(ListNode head) {
ListNode newhead=null;
ListNode prenode=null;
ListNode current=head;
ListNode nextnode=null;
while(current!=null) {
nextnode=current.next;
if(nextnode==null) {
newhead=current;
}
current.next=prenode;
prenode=current;
current=nextnode;
}
return newhead;
}
}
运行结果：
035679
976530
第二个问题：合并两个排序的链表
1. 题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
2. 解题思路
非递归：首先新建一个头节点用来存储新的合并的链表，然后依次比较两个链表的各个节点的值大小，排序。类似于“按大小把数值一个个串起来作为新的链表”
递归：和上述非递归的值比较方法一致，只不过用的是递归的方法。
3. 代码：
非递归代码一：
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
public class Merge {
public static void main(String[] args) {
// 定义节点
ListNode root1 = new ListNode(0) ;
ListNode n11 = new ListNode(1) ;
ListNode n12 = new ListNode(3) ;
ListNode n13= new ListNode(5) ;
ListNode n14 = new ListNode(7) ;
ListNode n15 = new ListNode(16) ;
// 连接节点
root1.next=n11;
n11.next=n12;
n12.next=n13;
n13.next=n14;
n14.next=n15;
// 定义节点
ListNode root2 = new ListNode(0) ;
ListNode n21 = new ListNode(5) ;
ListNode n22 = new ListNode(9) ;
ListNode n23 = new ListNode(10) ;
ListNode n24 = new ListNode(12) ;
ListNode n25 = new ListNode(14) ;
// 连接节点
root2.next=n21;
n21.next=n22;
n22.next=n23;
n23.next=n24;
n24.next=n25;
ListNode tmpnode1=root1;
while(tmpnode1!=null) {
System.out.print(String.valueOf(tmpnode1.val)+',');
tmpnode1=tmpnode1.next;
}
System.out.println();
ListNode tmpnode2=root2;
while(tmpnode2!=null) {
System.out.print(String.valueOf(tmpnode2.val)+',');
tmpnode2=tmpnode2.next;
}
System.out.println('\n');
ListNode newhead=Mer(root1,root2);
System.out.println('\n');
ListNode tmpnode3=newhead;
while(tmpnode3!=null) {
System.out.print(String.valueOf(tmpnode3.val)+',');
tmpnode3=tmpnode3.next;
}
}
public static ListNode Mer(ListNode list1,ListNode list2) {
if(list1==null) {
return list2;
}else if(list2==null){
return list1;
}
ListNode mergehead=new ListNode(-1);
ListNode root=mergehead;
while(list1!=null && list2!=null) {
if(list1.val<=list2.val) {
mergehead.next=list1;
System.out.println("h1:"+String.valueOf(mergehead.next.val));
mergehead=list1;
list1=list1.next;
}else {
mergehead.next=list2;
System.out.println("h2:"+String.valueOf(mergehead.next.val));
mergehead=list2;
list2=list2.next;
}
}
if(list1!=null){
mergehead.next=list1;
}
if(list2!=null){
mergehead.next=list2;
}
return root.next;
}
}
运行：
0,1,3,5,7,16,
0,5,9,10,12,14,
h1:0
h2:0
h1:1
h1:3
h1:5
h2:5
h1:7
h2:9
h2:10
h2:12
h2:14
0,0,1,3,5,5,7,9,10,12,14,16,
非递归代码二：
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
public class Merge {
public static void main(String[] args) {
// 定义节点
ListNode root1 = new ListNode(0) ;
ListNode n11 = new ListNode(1) ;
ListNode n12 = new ListNode(3) ;
ListNode n13= new ListNode(5) ;
ListNode n14 = new ListNode(7) ;
ListNode n15 = new ListNode(16) ;
// 连接节点
root1.next=n11;
n11.next=n12;
n12.next=n13;
n13.next=n14;
n14.next=n15;
// 定义节点
ListNode root2 = new ListNode(0) ;
ListNode n21 = new ListNode(5) ;
ListNode n22 = new ListNode(9) ;
ListNode n23 = new ListNode(10) ;
ListNode n24 = new ListNode(12) ;
ListNode n25 = new ListNode(14) ;
// 连接节点
root2.next=n21;
n21.next=n22;
n22.next=n23;
n23.next=n24;
n24.next=n25;
ListNode tmpnode1=root1;
while(tmpnode1!=null) {
System.out.print(String.valueOf(tmpnode1.val)+',');
tmpnode1=tmpnode1.next;
}
System.out.println();
ListNode tmpnode2=root2;
while(tmpnode2!=null) {
System.out.print(String.valueOf(tmpnode2.val)+',');
tmpnode2=tmpnode2.next;
}
System.out.println('\n');
ListNode newhead=Mer(root1,root2);
System.out.println('\n');
ListNode tmpnode3=newhead;
while(tmpnode3!=null) {
System.out.print(String.valueOf(tmpnode3.val)+',');
tmpnode3=tmpnode3.next;
}
}
public static ListNode Mer(ListNode list1,ListNode list2) {
if(list1==null) {
return list2;
}else if(list2==null){
return list1;
}
ListNode mergeHead = null;
ListNode current = null;
while(list1!=null && list2!=null){
if(list1.val <= list2.val){
if(mergeHead == null){
mergeHead = current = list1;
}else{
current.next = list1;
current = current.next;
}
list1 = list1.next;
}else {
if(mergeHead == null){
mergeHead = current = list2;
}else{
current.next = list2;
current = current.next;
}
list2 = list2.next;
}
}
if(list1 == null){
current.next = list2;
}else{
current.next = list1;
}
return mergeHead;
}
}
运行：
0,1,3,5,7,16,
0,5,9,10,12,14,
0,0,1,3,5,5,7,9,10,12,14,16,
递归代码：
public ListNode Mer(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val <= list2.val){
list1.next = Merge(list1.next, list2);
return list1;
}else{
list2.next = Merge(list1, list2.next);
return list2;
}
}
这样看来还是递归厉害，但基本思路还是上述的非递归中的思想。
仅作为自己学习的笔记。。
