链表
2020-02-08 本文已影响0人
isuntong
- 从尾到头打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(listNode == null) {
return list;
}
while(listNode!=null) {
list.add(listNode.val);
listNode = listNode.next;
}
Collections.reverse(list);
return list;
}
- 链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null) {
return null;
}
ListNode st = head;
int count = 0;
while(head != null) {
count++;
head = head.next;
}
if(count<k) {
return null;
}
count = count - k;
while(count != 0) {
st = st.next;
count--;
}
return st;
}
利用步长为k的两个指针去做
public ListNode FindKthToTail(ListNode head,int k) {
//一种思路是先遍历一遍求长度，然后输出倒数k个
//正常的思路是，设置两个游标,让快的领先k个
ListNode slow = head;
ListNode fast = head;
if (head == null || k <= 0) {
return null;
}
for (int i = 1; i < k; i++) { //快的先走k-1步，倒数第三个，其实应该快的指到第三个，只需要走两步即可。
if(fast.next == null) //这个是k与链表长度的关系，如果，链表长度小于k，肯定在走到k之前就出现
//null，直接返回null即可
return null;
else
fast = fast.next;
}
while(fast.next != null){ //快的从第k个，慢的从第1个，同时开始走。
slow = slow.next;
fast = fast.next;
}
return slow;
}
- 反转链表
输入一个链表，反转链表后，输出新链表的表头。
public ListNode ReverseList(ListNode head) {
if(head == null) {
return null;
}
if(head.next == null) {
return head;
}
ListNode temp = null;
ListNode ln1 = head;
ListNode ln2 = head.next;
head = head.next.next;
ln1.next = null;
while(head != null) {
temp = head;
ln2.next = ln1;
ln1 = ln2;
ln2 = temp;
head = head.next;
}
ln2.next = ln1;
return ln2;
}
答案：
public ListNode ReverseList(ListNode head) {
if (head == null)
return null;
ListNode pre = null;
ListNode next = null;
while(head != null){ //注意这个地方的写法，如果写head.next将会丢失最后一个节点
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
- 合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
if(list1 == null && list2 == null) {
return null;
}
if(list1 == null) {
return list2;
}
if(list2 == null) {
return list1;
}
ListNode st = new ListNode(-1);
ListNode tmp = st;
while(list1 != null && list2 != null) {
if(list1.val >= list2.val) {
tmp.next = list2;
tmp = tmp.next;
list2 = list2.next;
}else {
tmp.next = list1;
tmp = tmp.next;
list1 = list1.next;
}
}
tmp.next = list1==null?list2:list1;
return st.next;
- 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
答案：
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.HashMap;
public class Solution {
/**左程云思路：除了这个还有不用链表的思路。
* 算法步骤：遍历两遍链表，第一遍将仅仅将数赋值给map中的值，第二遍将指针指向赋值。注意保存头指针的位置。
* 1.第一遍遍历，key是第一个链表中的节点，value是复制后的链表节点，但是指针都指向null。
* 2.第二遍遍历，将相对应的next和random均复制。
* @param pHead
* @return
*/
public RandomListNode Clone(RandomListNode pHead)
{
HashMap<RandomListNode, RandomListNode> map =new HashMap<RandomListNode, RandomListNode>();
RandomListNode current = pHead; //保存头结点
while (current != null) {//第一遍遍历
map.put(current,new RandomListNode(current.label));// hashmap里面，key放的是之前的链表节点，value现在只放值
current = current.next;
}
current = pHead;
while (current != null) {//第二遍遍历
//现在map中是1--1' 2--2'。为了让1'指向2' 要给1'的next赋值， 要找1'就得get(1)。值是2',要找2'就是get(1.next)
map.get(current).next = map.get(current.next);
map.get(current).random = map.get(current.random);
current = current.next;
}
return map.get(pHead);
}
}
- 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
HashSet<ListNode> hs = new HashSet<>();
while(pHead1 != null) {
hs.add(pHead1);
pHead1 = pHead1.next;
}
while(pHead2 != null) {
if(hs.contains(pHead2)) {
return pHead2;
}
pHead2 = pHead2.next;
}
return null;
}
答案：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
/**采用了左程云的代码思想：
* 首先，如果相交，那么尾节点一定是一样的。
* 接下来，谁长谁就先走一定的步数，然后一起走，肯定是同时到达相交的点。
* @param pHead1
* @param pHead2
* @return
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null)
return null;
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
int n = 0;
while(cur1.next != null) {
n++; //记录长度
cur1 = cur1.next;
}
while(cur2.next != null) {
n--;
cur2 = cur2.next;
}
if(cur1 != cur2)
return null;
cur1 = n > 0 ? pHead1:pHead2;// n大于0 说明cur1要先走一部分。
cur2 = cur1 == pHead1 ?pHead2:pHead1;//cur2 等于另一个
n= Math.abs(n);
while(n !=0 ) {
n--; //先cur1走完这部分
cur1 = cur1.next;
}
while(cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}
- 链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
- 第一步，找环中相汇点。分别用p1，p2指向链表头部，
- p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
通过141题，我们知道可以通过快慢指针来判断是否有环，现在我们假设两个指针相遇在z点，如图
那么我们可以知道fast指针走过a+b+c+b
slow指针走过a+b
那么2*(a+b) = a+b+c+b
所以a = c
那么此时让slow回到起点，fast依然停在z，两个同时开始走，一次走一步
那么它们最终会相遇在y点，正是环的起始点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 主要思路就是一快 一慢两个指针，如果有环，最终快的肯定能追上慢的，
* 找环的入口的思路见博客。
* @param pHead
* @return
*/
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if (pHead == null || pHead.next == null) {
return null;
}
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next != null) {//因为fast每次要走两步，所有需要判断fast的下一个是否为空
slow = slow.next;
fast = fast.next.next;//一个走一步 一个走两步
if(slow == fast) {
fast = pHead;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
我的思路
HashSet有了，就是入口
- 删除链表中重复的节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead == null)
return null;
// 新建一个节点，防止头结点被删除
ListNode firstNode = new ListNode(-1);
firstNode.next = pHead;
ListNode p = pHead;
// 指向前一个节点
ListNode preNode = firstNode;
while (p!=null &&p.next !=null) {//注意条件的顺序，否则不对 因为如果p为null，p.next肯定异常
if(p.val == p.next.val) {
int val = p.val;
// 向后重复查找
while (p != null&&p.val == val) {
p = p.next;
}
// 上个非重复值指向下一个非重复值：即删除重复值
preNode.next = p;
}
else {
// 如果当前节点和下一个节点值不等，则向后移动一位
preNode = p;
p = p.next;
}
}
return firstNode.next;
}
