剑指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); // 从第一个与当前结点不同的结点开始递归
pHead.next = deleteDuplication(pHead.next); // 保留当前结点，从下一个结点开始递归
return pHead;
}
}
}
原文创作：程序员khaos
原文链接：https://www.cnblogs.com/urmkhaos/p/15394290.html
