合并两个有序链表:
方法一:递归
public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
if (list1==null) return list2;
if (list2==null) return list1;
if (list1.val>list2.val){
list2.next=mergeTwoLists(list1,list2.next);
return list2;
}
list1.next=mergeTwoLists(list1.next,list2);
return list1;
}
方法二:
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode res=new ListNode();
ListNode p=res;
while (list1!=null&&list2!=null){
if (list1.val<list2.val){
p.next=list1;
list1=list1.next;
}else{
p.next=list2;
list2=list2.next;
}
p=p.next;
}
while (list1!=null){
p.next=list1;
}
while (list2!=null){
p.next=list2;
}
return res.next;
}
删除有序链表中的重复元素,使得每个元素只出现一次:
递归实现:
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;
}
非递归实现:
public ListNode deleteDuplicates2(ListNode head) {
if (head==null||head.next==null){
return head;
}
//非递归方式实现
ListNode p=head;
while (p!=null&&p.next!=null){
if (p.val==p.next.val){
p.next=p.next.next;
}else{
p=p.next;
}
}
return head;
}
环形链表:
判断链表中是否存在环,使用快慢指针,快指针每次走两步,慢指针每次走一步,如果慢指针与快指针相与则存在环,否则无环。
public boolean hasCycle(ListNode head) {
if (head==null||head.next==null){
return false;
}
ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if (fast==slow){
return true;
}
}
return false;
}
环形链表II:
判断链表中是否存在环,如果存在,找到环的入口
public ListNode detectCycle(ListNode head) {
//快慢指针
if (head==null||head.next==null){
return null;
}
ListNode slow=head;
ListNode fast=head;
while (fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
if (slow==fast){
//相遇后,快指针回到起点,快慢指针每次个走一步,判断是否相与,
//再次相遇出就是入口
fast=head;
while (slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
}
return null;
}
相交链表:
方法一:pa=headA,pb=headB,不断遍历两个链表,如果指向null则指向另一个链表的头节点,当pa==pb时如果相交则是交点,如果不相交,则pa==pb==null,则不相交。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA==null||headB==null){
return null;
}
ListNode pa=headA;
ListNode pb=headB;
while (pa!=pb){
pa=pa==null?headB:pa.next;
pb=pb==null?headA:pb.next;
}
return pa;
}
方法二:;将headA的链表依次加入set中,然后遍历headB所在链表,判断节点是否存在。
public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
if(headB==null||headA==null){
return null;
}
Set<ListNode> set=new HashSet<>();
ListNode pa=headA;
while (pa!=null){
set.add(pa);
pa=pa.next;
}
ListNode pb=headB;
while (pb!=null){
if (set.contains(pb)){
return pb;
}
pb=pb.next;
}
return null;
}
方法三:遍历获得两个链表的长度,然后让较长的链表先走d个节点,然后,两个节点同时移动,如果相遇则相交,否则没有焦点
public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
//获得两个链表的长度
int lenA=0;
int lenB=0;
ListNode pa=headA;
while (pa!=null){
lenA++;
pa=pa.next;
}
ListNode pb=headB;
while (pb!=null){
lenB++;
pb=pb.next;
}
int d=Math.abs(lenA-lenB);
pa=headA;
pb=headB;
if (lenA>lenB){
while (d-->0){
pa=pa.next;
}
}else{
while (d-->0){
pb=pb.next;
}
}
while (pa!=pb){
pa=pa.next;
pb=pb.next;
}
return pa;
}
反转链表:
public ListNode reverseList(ListNode head) {
if (head==null||head.next==null){
return head;
}
ListNode preNode=null;
ListNode curNode=head;
while (curNode!=null){
ListNode next = curNode.next;
curNode.next=preNode;
preNode=curNode;
curNode=next;
}
return preNode;
}
判断回文链表:
使用快慢指针,慢指针移动到链表的中间节点,反转后半部分的链表,然后快指针移动到链表头节点,将反转后的链表依次比较。
public boolean isPalindrome(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
fast=head;
//反转链表
ListNode preNode=null;
ListNode curNode=slow;
while (curNode!=null){
ListNode next = curNode.next;
curNode.next=preNode;
preNode=curNode;
curNode=next;
}
//从preNode开始比较
while (preNode!=null){
if (fast.val!=preNode.val){
return false;
}
fast=fast.next;
preNode=preNode.next;
}
return true;
}
返回链表的中间节点:
public ListNode middleNode(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
删除链表中的倒数第k个节点:
使用快慢指针,将快指针先移动k-1次,然后快慢指针一起移动,当快指针到达链表末尾时,慢指针所指位置就是倒数第k个节点。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sen=new ListNode(-1,head); //哨兵节点
ListNode fast=head;
ListNode slow=sen;
while (n-->1){ //快指针移动k-1次
fast=fast.next;
}
while (fast.next!=null){ //当快指针到达最后一个节点
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next; //删除第k个节点
return sen.next;
}
**两两交换链表中的节点:
递归版:
public ListNode swapPairs(ListNode head) {
if (head==null||head.next==null){
return head;
}
ListNode p2=head.next;
head.next=swapPairs(p2.next);
p2.next=head;
return p2;
}
迭代版:
public ListNode swapPairs2(ListNode head) {
//想到了思路实现不出来,想到了哨兵节点,但是没想到tmp节点,真的是有思路不代表会写代码
ListNode sentinel=new ListNode(-1,head);
ListNode tmp=sentinel;
ListNode p1;
ListNode p2;
while (tmp.next!=null&&tmp.next.next!=null){
p1=tmp.next;
p2=tmp.next.next;
tmp.next=p2;
p1.next=p2.next;
p2.next=p1;
tmp=p1;
}
return head;
}