2022-01-09 链表

链表定义：

/**
 * 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;
     }
    
}