华为od面试手撕代码真题题型4—

华为od面试手撕代码真题题型4——链表

链表

1 单链表相交

160. 相交链表 - 力扣（LeetCode）

解法一指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历。如果 pA 到了末尾，则 pA = headB 继续遍历、如果 pB 到了末尾，则 pB = headA 继续遍历。如此长度差就消除了

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p = headA;ListNode q = headB;while(p != q){if (p == null) {p = headB;}else{p = p.next;}if (q == null){q = headA;}else{q = q.next;}}return p == null ? null : p;}

解法二先得到headA，headB的长度，让长的先走长度差的单位，然后再一起走并判断节点是否相同。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode p = headA;ListNode q = headB;int lenA = 0;int lenB = 0;//获取链表长度while (p != null){p = p.next;lenA ++;}while (q != null){q = q.next;lenB ++;}//p,q重新指向链表头p = headA;q = headB;if (lenA >= lenB){int n = lenA -lenB;while (n -- > 0){ //让p先走n步p = p.next;}}else {int n = lenB -lenA;while (n -- > 0){ //让q先走n步q = q.next;}}//然后一起走while (p != null && q != null){if (p == q) return p;p = p.next;q = q.next;}return null;}

2 判断链表是否有环

思路：双指针

876. 链表的中间结点 - 力扣（LeetCode）

141. 环形链表 - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

876 题解

 public ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;//fast != null && fast.next != null 最后slow指的就是中点（偶数的话中偏右）while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}

141 题解

 public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if (slow == fast) return true;}return false;}

142题解

public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if (slow == fast){ //达到相交点后 head到环头的长度等于快慢指针相交点到环头的距离while (head != slow){head = head.next;slow = slow.next;}return slow;}}return null;}