剑指offer计划链表

从尾到头打印链表

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> num = new ArrayList();
        ArrayList<Integer> res = new ArrayList();
        while(listNode!=null){
            num.add(listNode.val);
            listNode=listNode.next;
        }
		for(int i = num.size()-1;i>=0; i --){
            res.add(num.get(i));
        }
        
        return res;
    }
}

反转链表

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null) return null;
        ListNode pre = null;
        while(head!=null){
            ListNode next=head.next;
            head.next=pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

合并两个排序的链表

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(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;}
    }
}

两个链表的第一个公共结点

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.HashSet;

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> hashset = new HashSet<ListNode>();
        if(pHead1==null || pHead2==null) return null;
        while(pHead1!=null) {
            hashset.add(pHead1);
             pHead1= pHead1.next;
        }
        while(pHead2!=null){
            if(hashset.contains(pHead2)) return pHead2;
            pHead2= pHead2.next;
        }
        return null;
        
        
    }
}

链表中环的入口结点

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashSet<ListNode> hashset = new HashSet();
        while(pHead!=null){
            if(hashset.contains(pHead)){
                return pHead;
            }
            hashset.add(pHead);
            pHead = pHead.next;
        }
        return null;
        
    }
}

链表中倒数最后k个结点

    public ListNode FindKthToTail(ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        int count = 0;
        ListNode temp = pHead;
        while (temp!=null) {
            count ++ ;
            temp = temp.next;
        }
        if (count < k) {
            return null;
        }
        temp = pHead;
        for (int i = 0; i < count - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

复杂链表的复制

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
        Map<RandomListNode, RandomListNode> cachedNode = new HashMap<RandomListNode, RandomListNode>();
        public RandomListNode Clone(RandomListNode pHead) {
         if (pHead == null)   return null;
        if (!cachedNode.containsKey(pHead)) {
            RandomListNode headNew = new RandomListNode(pHead.label);
            cachedNode.put(pHead, headNew);
            headNew.next = Clone(pHead.next);
            headNew.random = Clone(pHead.random);
        }
        return cachedNode.get(pHead); 
    }
}

删除链表中重复的结点

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) { // 只有0个或1个结点，则返回
            return pHead;
        }
        if (pHead.val == pHead.next.val) { // 当前结点是重复结点
            ListNode pNode = pHead.next;
            while (pNode != null && pNode.val == pHead.val) {
                // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
                pNode = pNode.next;
            }
            return deleteDuplication(pNode); // 从第一个与当前结点不同的结点开始递归
        } else { // 当前结点不是重复结点
            pHead.next = deleteDuplication(pHead.next); // 保留当前结点，从下一个结点开始递归
            return pHead;
        }
    }
}