链表相关题解

一、两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution{
	public ListNode addTwoNumbers(ListNode l1,ListNode l2){
		ListNode pre =new ListNode(0);
		ListNode cur =pre;
		int carry = 0;
		while(l1!=null||l2!=null){
			int x =l1==null? 0:l1.val;
			int y =l2==null? 0:l2.val;
			int sum = x+y+carry;
			carry =sum/10;
			sum=sum%10;
			cur.next = new ListNode(sum);
			cur=cur.next;
			if (l1!=null){
				l1=l1.next}
			if(l2!=null){
				l2=l2.next;}
			
					

}
	if(carry==1){
		cur.next = new ListNode(1);}
	}
return pre.next;

}

二、删除链表的倒数第N的节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

Class Solution
	public ListNode removeNthFormEnd(ListNode head,int n){
		ListNode pre = new ListNode(0);
		pre.next = head;
		ListNode start = pre;
		ListNode end =pre;
		while(n!=0){
			start = start.next;
			n--;}
		while(start.next!=null){
			start = start.next;
			end = end.next;}
		end.next=end.next.next;
		}
		return pre;

三、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur =pre;
        while(l1!=null&&l2!=null){
           if(l1.val>l2.val){
               cur.next=l2;
               l2=l2.next;
           }else{
               cur.next=l1;
               l1=l1.next;
           }
           cur=cur.next;
     
        }
        cur.next= l1==null? l2:l1;
        return pre.next;
        

    }
}

四、复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。

class Solution{
	public Node copyRandomList(Node head){
		if(head==null){
		return head;}
		HashMap<Node,Node> map =new HashMap<>();
		Node p =head;
		while(p!=null){
			Node newNode = new Node(p.val);
			map.put(p,newNode);
			p=p.next;
		
			}
		p=head;
		while(p!=null){
			Node newNode = map.get(p);
			if(p.next!=null){
				newNode.next=map.get(p.next);
				}
			if(p.random!=null){
				newNode.random = map.get(p.random);}
                p=p.next;
			}
			
		
		return map.get(head);
		}
		}

五、环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false

public class Solution{
	public boolean hasCycle(ListNode head){
		if(head==null){
		return false;}
		ListNode fast = head.next;
		ListNode slow = head;
		while(fast!=null&&fast.next!=null){
			slow = slow.next;
			fast = fast.next.next;
			if(slow==fast){
					return true;
			}
			}
		retuen false;
		

}
}

六、LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

class LRUCache{
	class Node{
		public int key,val;
		public Node next,prev;
		public Node(int k,int v){
			this.key = k;
			this.val = val;
				}
				
		}
	class doubleList{
		private Node head,tail;
		private int size;
		public void addFirst(Node node){
			if(head==null){
				head = tail= node;
			}else{
				Node n = head;
				n.prev = node;
				node,next = n;
				head = node; 
			}
			size++;
			
			}
		public void remove(Node node){
			if(head == node&&tail == node){
				head = null;
				tail = null;}
			else if(tail == node){
			 	node.prev.next = null;
			 	tail = node.prev;
			 }else if(head==node){
			 	node.next,prev = null;
			 	head= node.next;}
			 else{
			 	node.prev.next = node.next;
			 	node.next.prev = node.prev;}
			 size--;}
		public Node removeLast(){
			Node node =tail;
			remove(tail);
			return Node;}
		public size(){
			return size;}}
private HashMap<Integer,Node> map;
private doubleList cache;
private int cap;

	public LRUCache(int cap){
		this.cap=cap;
		map = new HashMap<>();
		cache = new doubleList();
		
	}
	public int get(int key){
		if(map.containsKey(key)){
       		int val = map.get(key).val;
       		put(key.val);
       		return val;


		}return -1;
		}
	public int put(int key,int value){
		Node x = new Node(key,value)
		if(map.containsKey(key)){
			cache.remove(map.get(key));
			cache.addFirst(x);
			map.put(key,x);}
		}else{
			if(cap==cache.size()){
				Node last=cache.removeList();
				map.remove(last.key);

		}	cache.addFirst(x);
			map.put(key,x);
		}
		
		










}

七、排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode fast =head.next;
        ListNode slow =head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next=null;
        
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode pre = new ListNode(0);
        ListNode cur=pre;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                cur.next = left;
                left=left.next;
                cur=cur.next;
            }else{
                cur.next=right;
                right=right.next;
                cur=cur.next;
            }

            

        }
        cur.next=left==null?right:left;
        return pre.next;

    }
}

八、相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode la =headA;
        ListNode lb =headB;
        while(la!=lb){
            if (la!=null){
                la=la.next;
            }else{
                la=headB;
            }
            lb=lb==null? headA:lb.next;
        }
        return la;
       


            }
        }

九、反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ListNode tmp= reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return tmp;

    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
       ListNode pre =null;
       ListNode cur = head;
       ListNode tmp = null;

      while(cur!=null){
          tmp = cur.next;
          cur.next=pre;
          pre=cur;
          cur=tmp;


      }
      return pre;

    }
}

十、反转链表

请判断一个链表是否为回文链表。

  public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }

十一、删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点

class Solution {
    public void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;

        
    }
}

十二、奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数

class Solution {
    public ListNode oddEvenList(ListNode head) {
    	if(head==null){
    		return head;}
     
        ListNode odd=head;
        ListNode even = head.next;
        ListNode evenhead = even;
        while(even.next!=null&&even!=null){
            odd.next = even.next;
            odd=odd.next;
            even.next= old.next;
            even=odd.next;
            
            
        }
        odd.next= evenhead;

    }
    return head;
}