链表定义：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
反转链表：
用到了之前写的ArrayDeque来当作栈使用，因为ArrayDeque的方法可以作栈和队列。
采用栈的特性进行了链表的反转。
java版本
class Solution {
public ListNode reverseList(ListNode head) {
ArrayDeque<Integer> stack=new ArrayDeque<>();
ListNode temp=head;
while(temp!=null){
stack.add(temp.val);
temp=temp.next;
}
ListNode ans=new ListNode();
ListNode res=ans;
if(stack.size()==0){
return head;
}
res.val=stack.pollLast();
while(stack.size()!=0){
ListNode tmp=new ListNode();
tmp.val=stack.pollLast();
res.next=tmp;
res=res.next;
}
return ans;
}
}
剑指 Offer II 025. 链表中的两数相加
反转两个链表的基础上依次相加即可。注意考虑两个链表长度不一致和相加进位的情况
java版本
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 两个链表倒过来逐个相加
ListNode l1_rev=reverseList(l1);
ListNode l2_rev=reverseList(l2);
int count=0;
ListNode ans=new ListNode();
ListNode res=ans;
res.val=0;
while(l1_rev!=null && l2_rev!=null){
ListNode tmp=new ListNode();
tmp.val=l1_rev.val+l2_rev.val+count;
if(tmp.val>=10){
tmp.val=tmp.val-10;
count=1;
}else{
count=0;
}
res.next=tmp;// ?
res=res.next;
l1_rev=l1_rev.next;
l2_rev=l2_rev.next;
}
// 确定哪一个还有值
ListNode temp=null;
if( l1_rev!=null){
temp=l1_rev;
}
if( l2_rev!=null){
temp=l2_rev;
}
while(temp!=null || count!=0){
ListNode tmp=new ListNode();
if(temp==null){
temp=new ListNode();
temp.val=0;
}
tmp.val=temp.val+count;
if(tmp.val>=10){
tmp.val=tmp.val-10;
count=1;
}else{
count=0;
}
res.next=tmp;// ?
res=res.next;
temp=temp.next;
}
return reverseList(ans.next);
}
public ListNode reverseList(ListNode head) {
ArrayDeque<Integer> stack=new ArrayDeque<>();
ListNode temp=head;
while(temp!=null){
stack.add(temp.val);
temp=temp.next;
}
ListNode ans=new ListNode();
ListNode res=ans;
if(stack.size()==0){
return head;
}
res.val=stack.pollLast();
while(stack.size()!=0){
ListNode tmp=new ListNode();
tmp.val=stack.pollLast();
res.next=tmp;
res=res.next;
}
return ans;
}
}
026重排链表：
Go 新建链表节点 ans:=&ListNode{Val:head.Val};
go版本：
func reorderList(head *ListNode) {
// // 还不如重新建个链表，根据顺序慢慢放值
res:=head;
var arr []int;
var get []int;
for{
if(head==nil){
break;
}
arr=append(arr,head.Val);
head=head.Next;
}
get=append(get,arr[0])
length:=len(arr);
for i:=1;i<length;i++{
if i%2==0{
get=append(get,arr[int(i/2)])
}else{
get=append(get,arr[length-int(i/2)-1]);
}
}
res.Val=get[0];
for i:=1;i<length;i++{
temp:=&ListNode{Val:get[i]}
res.Next=temp;
res=res.Next;
}
}
