一、合并两个有序链表
将两个升序链表合并为一个升序链表后返回,新链表是通过拼接两个链表的节点组成的
思路:分别比较两个链表头部的节点,将较小节点的连接到新链表后
public ListNode mergeTwoList(ListNode l1,ListNode l2)
{
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode resultNode = new ListNode(0);
ListNode p = resultNode;
while(l1 != null && l2 != null)
{
if(l1.val < l2.val)
{
p.next = l1;
l1 = l1.next;
}
else
{
p.next = l2;
l2 = l2.next;
}
}
if(l1 != null)
p.next = l1;
if(l2 != null)
p.next = l1;
return resultNode.next;
}
算法2:使用递归进行解决
public ListNode mergeTwoList(ListNode l1,ListNode l2)
{
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val)
{
l1.next = mergeTwoList(l1.next,l2);
return l1;
}
l2.next = mergeTwoList(l1,l2.next);
return l2;
}
二、删除链表中重复的元素
有一个按升序排列的链表,请删除所有重复的元素,使每个元素只出现一次。
思路:当前节点的值若与下一节点的值相等,令当前节点越过重复结点指向下一结点。
public ListNode deleteDuplicates(ListNode head)
{
if(head == null)
return head;
ListNode currentNode = head;
while(null != currentNode.next)
{
if(currentNode.next.val == currentNode.val)
currentNode.next = currentNode.next.next;
else
currentNode.next = currentNode.next;
}
return head;
}
算法2:递归处理(等于压栈后倒序处理)
public ListNode = deleteDuplicates(ListNode head)
{
if(head == null || head.next == null)
return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;//是否越过下一元素
}
三、环形链表
给定一个链表,判断链表中是否有环
思路:使用hash表来解决(逐个遍历--略)
通用解法:弗洛伊德解法(快指针(每次两个结点)+慢指针(每次一个节点)),如果两个指针相遇则说明此链表有环(追击问题)
public bool hashCycle(ListNode head)
{
if(head == null) return false;
ListNode slowPtr = head , fastPtr = head;
while(fastPtr.next != null && fastPtr.next.next !=null)
{
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
if(slowPtr == fastPtr)
return ture;
}
return false;
}
进阶:额外给出该链表第一个入环的节点
思路:找到环以后将慢指针指向头结点,快慢指针继续移动(同步移动)
public bool hashCycle(ListNode head)
{
if(head == null) return false;
ListNode slowPtr = head , fastPtr = head;
bool loopExists = false;
while(fastPtr.next != null && fastPtr.next.next !=null)
{
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
if(slowPtr == fastPtr)
{
loopExists = true;
break;
}
}
if(loopExists)//环存在
{
slowPtr = head;
while(slowPtr != fastPtr)
{
fastPtr = fastPtr.next;
slowPtr = slowPtr.next;
}
return slowPtr;//返回开始结点
}
return null;//环不存咋
}
四、相交链表
给定两个头结点为headA和headB的链表,若两个链表存在交点则返回该交点,否则返回null
思路:暴力遍历(将其中一个链表的节点与另一个链表中的节点进行比较)O(M×N)
思路2:引入hash表O(M+N)
思路3:使用双指针(当某个指针移动到末尾时让其指向另一个链表的头部,如此往复总有一刻会汇聚在交点<不存在的话会同时指向null>)O(M+N)
public ListNode getIntersectionNode(ListNode headA,ListNode headB)
{
if(headA == null || headB == null)
return null;
ListNode pA = headA, pB = headB;
while(pA != pB)
{
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
思路3:计算出两个链表的长度差,使长的链表从第n个元素开始遍历(n为长度差),如果有交点则会在交点处相交
五、反转链表
给定头结点head,求反转后的链表
思路:使用双结点(引入一个preNode指向前一节点,用来调转方向)
public ListNode reverseList(ListNode head)
{
ListNode preNode = null;
ListNode curr = head;
while(curr != null)
{
ListNode next = curr.next;
curr.next = preNode;
preNode = curr;
curr = next;
}
return next;
}
六、回文链表
给定一个链表,判断是否为回文链表
思路:如果是双链表,则在首位各放置一个指针,相同则移动,不相同则返回false
思路2:使用双指针(使用快慢指针找到链表的中间位置,然后将后半部的链表进行反转<分奇偶进行>)
public bool isPalindrome(ListNode head)
{
ListNode fast = head, slow = head;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
//如果为奇数结点,则将正中点归到左边
if(fast != null)
slow = slow.next;
slow = reverse(slow);
fast = head;
while(slow != null)
{
if(fast.val != slow.val)
return null;
fast = fast.next;
slow = slow.next;
}
return true;
}
七、中间结点
给定一个链表,返回中间结点,如果有两个中间结点则返回第二个
思路:长度/2(需要至少遍历一次,两次循环)
思路2:使用双指针(快慢指针,同上题)
public ListNode middleNode(ListNode head)
{
ListNode fast = head, slow = head;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
八、链表导数第K个结点
思路:将目标指针先移动k-1个结点,然后开始双指针遍历
public ListNode KthNodeFromEnd(ListNode head,int kthNode)
{
if(kthNode<=0 || head == null)
return null;
ListNode pTemp = head, pkthNode = null;
for(int count = 1;count<kthNode;count++)
if(pTemp != null)
pTemp = pTemp.next;
while(pTemp != null)
{
if(pkthNode == null)
pkthNode = head;
else
pkthNode = pkthNode.nextl
pTemp = pTemp.next;
}
if(pkthNode != null)
return pkthNode;
return null;
}
九、总结
链表相关的问题,可以优先使用双指针进行考虑(快慢指针/间隔指针),实在不行可以进行暴力遍历