链表经典操作与实战

一、前言

算法是计算机软件的基础，今年打算深入学习一些算法，记录一些算法理论以及最佳实践，希望可以坚持下去。

二、链表定义与分类

链表是通过指针关联数据节点的一种存储结构。

public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

根据指针方向可以分为单向链表、双向链表以及环形链表。

• 单向链表

• 双向链表

• 环形链表

三、链表的几类经典操作

• 设置虚拟头节点

第一点，通过给链表设置虚拟头节点，可以保证头节点动作和其他非头节点操作逻辑一致。

比如下面例子，我们需要删除头节点1，我们只需要使用虚拟头节点指向头节点的next节点即可。

和假如我们需要删除第二个节点，那么会使用下面的方法，这个操作逻辑和上面逻辑一致。这就是使用虚拟头节点非常重要的一个好处。

第二点，通过设置虚拟头节点，我们处理完链表之后还能方便取到头节点。只需要使用dumy.next即可获取到头节点。

• 双指针法遍历链表

双指针法遍历链表对反转链表非常有用。比如有两个指针遍历下面链表。

• 先定位前驱节点

这个操作是一个经验，我们需要对某个节点P执行删除或者修改时，我们先找他他的前驱节点，这样操作节点P更加方便。

上面找到了节点P的前驱节点Prev,使用节点Prev操作节点P会更加便利。

• 遇到相交的链表，相交后的链表路径相同

四、热点链表题目实战

leetCode206. 反转链表

这个题目就是双指针遍历链表的经典应用。一个前驱节点（用于当前节点反转指向的新节点），一个当前节点（需要反转的节点）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode prev = null; //前驱节点
        ListNode curr = head; //当前节点

        while(curr != null) {

           ListNode temp = curr.next;
           //反转
           curr.next = prev;
           //当前节点变成前驱节点
           prev = curr;
           //当前节点指向下一个需要反转的节点
           curr = temp;
        }
        return prev;
    }
}

leetcode两两翻转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        //虚拟头节点指向头节点
        ListNode dumy = new ListNode();
        dumy.next = head;
        //当前节点指向虚拟节点，next,next.next是需要操作的节点
        ListNode curr = dumy;

        //执行两两交换
        while(curr.next != null && curr.next.next != null) {

            ListNode temp = curr.next;
            ListNode temp1 = curr.next.next;
            ListNode temp3 = curr.next.next.next;

            //执行两两翻转
            temp1.next =temp;
            curr.next = temp1;
            temp.next = temp3;

            //curr重新移动两个位置
            curr = curr.next.next;
        }
       
        return dumy.next;
    }
}

Curr指针指向需要翻转节点的前驱节点。

执行3步完成翻转。

这道题目使用到了虚拟头节点、定位到前驱节点经典操作，对于解题提供了极大的便利。

leetcode 面试题 02.07. 链表相交

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //如果相交，那么后面的节点和长度是一致的。
        ListNode currA = headA;
        int lenA = 0;
        while(currA != null) {
            lenA++;
            currA = currA.next;
        }

        ListNode currB = headB;
        int lenB = 0;
        while(currB != null) {
            lenB++;
            currB = currB.next;
        }

        if(lenA > lenB) {
         int gap =   lenA - lenB;
         while(gap > 0) {
             headA = headA.next;
             gap--;
         }
        } else {
            int gap =   lenB - lenA;
         while(gap > 0) {
             headB = headB.next;
             gap--;
         }

        }

        if(headA == headB) {
            return headA;
        }

        while(headA != null) {
             headA = headA.next;
             headB = headB.next;

             if(headA == headB) {
                 return headA;
             }

         }

         return null;
        
    }
}

这道题目解题的关键依据是遇到相交的链表，相交后的链表路径相同

2024加油，深入理解算法，学习算法，一起学习。