Java链表应用

大家好，又见面了，我是你们的朋友全栈君。

链表类

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

    ListNode(int val) {
        this.val = val;
    }
}

1、返回倒数第k个结点

前后指针法

需要考虑k大于链表长度的情况

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0) {
        	return null;
        }
        ListNode pre = head;
        ListNode cur = head;
        for(int i = 0; i <k -1; i++) {
        	if(cur == null) {
        		return null;//处理k大于链表长度的情况
        	}
        	cur = cur.next;
        }
        if(cur == null) {
        	return null;
        }
        while(cur.next != null) {
        	pre = pre.next;//前后指针
        	cur = cur.next;
        }
        return pre;
    }
}

2、返回两个无环链表的交点

public class Solution2 {
	
	public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		 int length1 = getListLength(pHead1);
		 int length2 = getListLength(pHead2);
		 int lengthD = length1 - length2;
		 ListNode pLong = pHead1;
		 ListNode pShort = pHead2;
		 if(length1 < length2) {
			 pLong = pHead2;
			 pShort = pHead1;
			 lengthD = -lengthD;
		 }
		 //长链表先走lengthD的长度
		 for(int i = 0; i < lengthD; i++) {
			 pLong = pLong.next;
		 }
		 //两个链表同步走，值相等时停止返回
		 while(pLong != null && pShort != null && pLong != pShort) {
			 pLong = pLong.next;
			 pShort = pShort.next;
		 }
		 return pShort;
    }

	private int getListLength(ListNode pHead1) {
		int length = 0;
		ListNode node = pHead1;
		while(node != null) {
			length++;
			node = node.next;
		}
		return length;
	}
}

3、删除排序链表的重复结点，重复结点不保留 

public class Solution3 {
	public ListNode deleteDuplication(ListNode pHead){
		if(pHead == null || pHead.next == null) {
			return pHead;
		}
		
		if(pHead.val == pHead.next.val) {
			ListNode aft = pHead.next;
			while(aft != null && aft.val == pHead.val) {//跳过所有相同的值，找到第一个不同的值
				aft = aft.next;
			}
			return deleteDuplication(aft);//从第一个不同的值继续递归
		}
		else {
			//当前没有重复元素，就从下一个节点开始
			pHead.next = deleteDuplication(pHead.next);
			return pHead;
		}
    }
}

4、输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

将该链表的值保存在栈中

新建链表，添加栈pop的值

public class Solution4 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> arrayList = new ArrayList<>();
        while(!stack.isEmpty()){
            arrayList.add(stack.pop());
        }
        return arrayList;
    }
}

5、右旋单链表，使每个结点向右移动n个位置，n为非负数

public class Solution5 {
	public ListNode rotateRight(ListNode head, int n) {
	    if(head == null || head.next == null || n == 0){
	        return head;
	    }
	 
	    int len = getLength(head);
	    if(n % len == 0) {
	    	return head;
	    }else {
	    	n %= len;
	    }
	    
	    ListNode mid = head;
	    ListNode pre = head;
	    for(int i = 0; i < len - n; i++){
	        pre = mid;
	        mid = mid.next;
	    }
	    pre.next = null;
	    ListNode newHead = mid;
	    while(mid.next != null){
	        mid = mid.next;
	    }
	    mid.next = head;
	    return newHead;
	}
	private int getLength(ListNode head){
	    ListNode node = head;
	    int len = 0;
	    while(node != null){
	        len++;
	        node = node.next;
	    }
	    return len;
	}
}

6、删除单链表中从后往前数的第n个结点

public class Solution6 {
	public ListNode removeNthFromEnd(ListNode head, int n) {
	    if(head == null){
	        return null;
	    }
	    
	    if(n <= 0){
	        return head;
	    }
	    
	    //前后指针
	    ListNode pre = head;
	    ListNode cur = head;
	    int i = 0;
	    for(; i < n && cur != null; i++){
	        cur = cur.next;
	    }
	    if(i < n) {//处理n大于链表长度的情况
	    	return head;
	    }
	    if(cur == null) {//头删
	    	head = head.next;
	    	return head;
	    }
	    
	    //cur与pre相差n-1个位置
	    //cur = null， pre在n+1处
        while(cur.next != null){
            pre = pre.next;
            cur = cur.next;
        }
        //删除pre
        pre.next = pre.next.next;
        
	    return head;
	}
}

7、反转链表

public class Solution7 {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        
        //三个指针遍历
        ListNode pre = null;
        ListNode node = head;
        ListNode aft = head.next;
        while(node != null){
            node.next = pre;
            pre = node;
            node = aft;
            if(aft != null){
                aft = aft.next;
            }
            else{
                aft = null;
            }
        }
        return pre;
    }
}