1,合并两个有序链表
我们先定义一个虚拟节点newH, 然后按照上图所走,但是当其中一个链表走空时,我们只需返回另一个链表即可
class Solution {public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode newhead =new ListNode();ListNode tmp = newhead;while(headA != null && headB != null){if(headA.val<headB.val){tmp.next=headA;headA=headA.next;tmp=tmp.next;}else{tmp.next=headB;headB=headB.next;tmp=tmp.next;}}if(headA==null){tmp.next=headB;}if(headB==null){tmp.next=headA;}return newhead.next;}
}
2,回文链表
我们第一步先找中间节点,然后翻转中间节点以后的部分,再设置循环让 head= head.next;
与 slow = slow.next;一步一步对比是否一致,一致则证明是回文链表
如果链表为偶数长度则比较head.next ==slow,如果一致则为回文链表
public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereif(head == null){return true;}//找中间节点ListNode fast = head;ListNode slow = head;while(fast != null && fast.next!=null){fast = fast.next.next;slow = slow.next;}//翻转链表ListNode cur = slow.next;while(cur !=null){ListNode curN=cur.next;cur.next = slow;slow = cur;cur = curN;}//slow从后往前 head从 前往后 直到相遇while(head!=slow){if(head.val != slow.val){return false;}if(head.next ==slow){return true;}head= head.next;slow = slow.next;}return true;}
}
3,相交链表
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//假设A链表长ListNode pl = headA;ListNode ps = headB;int lenA =0;int lenB = 0;while(pl != null){lenA++;pl = pl.next;}while(ps != null){lenB++;ps = ps.next;}//要重新赋值pl=headA;ps=headB;int len = lenA - lenB;//2,判断len是证书还是负数if(len <0){pl =headB;ps = headA;len = lenB- lenA;}//上述代码走完pl指向最长链表ps指向最短链表//len一定为正数//3,让长链表pl走 len步while(len != 0){pl=pl.next;len--;}//4,一起走直到相遇while(pl != ps){pl = pl.next;ps = ps.next;}if(pl == null){//如果两个引用都为空 返回nullreturn null; }return pl;}
}