链表

定义链表

1
2
3
4
5
public class ListNode {
    int val; //数据域
    ListNode next; //指针域
    ListNode(int val) { this.val = val; next=null;}//构造方法 指针域指向空
}

构造链表的方法

1
2
3
4
5
6
7
8
9
//headA [4,1,8,4,5]
ListNode headA = new ListNode(4);
headA.next = new ListNode(1);
ListNode c = new ListNode(8);
ListNode d = new ListNode(4);
ListNode e = new ListNode(5);
headA.next.next = c;
headA.next.next.next = d;
headA.next.next.next.next = e;

交叉链表leetcode

找到两个链表的交叉点(交叉点的地址相同)

1
2
3
4
5
6
7
8
9
10
11
12
13
//headA [4,1,x,4,5] headB [5,6,1,x,4,5]
//双指针实现逻辑 A+B B+A相同的地方
//[4 1 x 4 5 5 6 1 x 4 5]
//[5 6 1 x 4 5 4 1 x 4 5]
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;
}