【代码随想录】链表专栏（Java）

链表理论简介

链表长度不固定，增删快，查询慢。

移除链表元素 leetcode-203

/**
     * 203. 移除链表元素 （注意本题不带头节点！！！）
     * @param head
     * @param val
     * @return
     */
public ListNode removeElements(ListNode head, int val) {
    if(head==null ) return null;
    ListNode fakeHead = new ListNode();
    fakeHead.next = head; //创建虚拟头节点，方便头节点的删除
    ListNode cur = head;
    ListNode pre = fakeHead;
    while (cur != null){
        if(cur.val == val){
            pre.next = cur.next;
        }else {
            pre = cur;
        }
        cur =cur.next;
    }
    return fakeHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

反转链表 leetcode-206

/**
     * 反转链表 leetcode-206
     * @param head
     * @return
     */
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode pre = null;
    while (cur != null){
        ListNode curNext = cur.next;
        cur.next = pre;
        pre = cur;
        cur = curNext;
    }
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归：

public static ListNode reverseLinkedList(ListNode head) {
	  if (head == null || head.next == null) return head;
	  ListNode node = reverseLinkedList(head.next);
	  ListNode headNext = head.next;
	  headNext.next = head;
	  head.next = null;
	  return node;
}
1
2
3
4
5
6
7
8

两两交换节点 leetcode-24

/**
     * 两两交换链表中的节点 1->2->3->4 变为 2->1->4->3
     * @param head
     * @return
     */
public ListNode swapPairs(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode fakeHead = new ListNode(-1); //创建虚拟头节点 操作更为简单
    fakeHead.next = head;
    ListNode cur = fakeHead;
    while (cur.next != null && cur.next.next != null){
        ListNode curNext = cur.next; //当前节点的下一节点
        ListNode curNextNext = curNext.next; //当前节点的下下个节点
        ListNode curNextNextNext = curNext.next.next; //当前节点的下下下个节点

        cur.next = curNextNext; //fakeHead->2
        curNextNext.next = curNext; // 2->1
        curNext.next = curNextNextNext; // 1->3

        cur = cur.next.next;  //cur向后移动两位 cur此时在3的位置，3相当于头节点
    }

    return fakeHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

删除倒数第n个节点 leetcode-19

/**
     * 19. 删除链表的倒数第 N 个结点
     * @param head
     * @param n
     * @return
     */
public ListNode removeNthFromEnd(ListNode head, int n) {
    //为了方便操作，设置虚拟头节点
    ListNode fakeHead = new ListNode(-1);
    fakeHead.next = head;
    ListNode fastPointer = fakeHead;  // 设置快慢指针
    ListNode slowPointer = fakeHead;
    for (int i = 0; i <= n; i++) {  //快指针先往后走n+1步
        fastPointer = fastPointer.next;
    }
    while (fastPointer != null){
        fastPointer = fastPointer.next;
        slowPointer = slowPointer.next;
    }
    //循环结束，slowPointer 指向待删除节点的前一个节点
    slowPointer.next = slowPointer.next.next;
    return fakeHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

链表相交 leetcode-160

/**
     * 相交链表
     * @param headA
     * @param headB
     * @return
     */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int len1 = getLen(headA);
    int len2 = getLen(headB);
    if(len1 < len2){ //始终让headA成为长链表的头节点
        ListNode temp = headA;
        headA = headB;
        headB = temp;
    }
    int gap = Math.abs(len2 - len1);
    while (gap>0){ //长的先走，走的距离为长短的差值
        headA = headA.next;
        gap--;
    }

    while (headA != null && headB != null){
        if(headA == headB){
            break;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

/**
     * 返回链表的长度
     * @param head
     * @return
     */
public int getLen(ListNode head){
    int count = 0;
    while (head != null){
        count++;
        head = head.next;
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

环形链表 leetcode-142

/**
     * 环形链表 leetcode-142
     * @param head
     * @return
     */
public ListNode detectCycle(ListNode head) {
    //设置快慢指针，快指针每次走两步，慢指针走一步，若有环，则一定相遇
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){ //快慢指针相遇
            ListNode pointer1 = slow;
            ListNode pointer2 = head;
            while (pointer1 != pointer2){ 
                pointer1 = pointer1.next;
                pointer2 = pointer2.next;
            }
            return pointer2;
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解析参考：代码随想录 (programmercarl.com)