链表

2021-01-02

链表

Java

class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

C++

struct ListNode {
	int val;
 	ListNode *next;
 	ListNode() : val(0), next(nullptr) {}
 	ListNode(int x) : val(x), next(nullptr) {}
 	ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

1. 反转链表

反转一个单链表。这是Leetcode 206号问题。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode *dummy = new ListNode(0), *tmp;
        while(head != NULL){
            tmp = head->next;
            head->next = dummy->next;
            dummy->next = head;
            head = tmp;
        }
        return dummy->next;
    }
};

2. 环形链表

给定一个链表，判断链表中是否有环。这是Leetcode 141号问题。

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

3. 相交链表

编写一个程序，找到两个单链表相交的起始节点。这是Leetcode 160号问题。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         if (headA == null || headB == null)
            return null;
        int lena = 0, lenb = 0;
        ListNode heada = headA, headb = headB;
        while(heada!=null){
            heada = heada.next;
            lena++;
        }
        while(headb!=null){
            headb = headb.next;
            lenb++;
        }
        if(lena > lenb){
            for(int i = 1; i <= lena - lenb; i++ )
                headA = headA.next;
        }else{
            for(int i = 1; i <= lenb - lena; i++)
                headB = headB.next;
        }
      while(headA != null && headB != null){
            if(headA == headB){
                break;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

4. 链表的中间节点

快慢指针

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL){
            return head;
        }
        ListNode *slow = head, *fast = head;
        while(slow != NULL && fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

值得注意的是：当链表长度为奇数时，fast最后指向最后一个节点:1->3->5…；当链表长度为偶数，fast最后为空.

5. 链表的倒数第k个节点

快慢指针，先让快指针走k步，之后快慢指针一起走，当快指针为空时，慢指针恰好走到倒数第k个节点。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        for(int i = 1; i <= k && fast != null; i++){
            fast = fast.next;
        }
        while(head != null && fast != null){
            head = head.next;
            fast = fast.next;
        }
        return head;
    }
}

6. 重排链表

链表中间节点+反转后半个链表+合并两个链表（基本包含了常用的对链表的操作，具有代表性）

class Solution {
public:
    void reorderList(ListNode* head) {
            if(head == NULL){
        return ;
    }
    // 长度为1或者2
    if(head->next == NULL || head->next->next == NULL){
        return ;
    }
    // 1.快慢指针找到链表的中间节点
    // 2.反转中间节点以后的链表
    // 3.将反转后的链表插入前半个链表
    ListNode *slow = head, *fast = head;
    while(slow != NULL && fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }

    // slow 指针指向中间节点,反转
    ListNode *dummy = new ListNode(0), *tmp;
    // 断开中间节点与后半部分链表的链接，可能会出现环
    tmp = slow->next;
    slow->next = NULL;
    slow = tmp;
    while(slow != NULL){
        tmp = slow->next;
        slow->next = dummy->next;
        dummy->next = slow;
        slow = tmp;
    }
    dummy = dummy->next;

    // 合并两端长度相差不超过1的链表
    ListNode *tmp1 = NULL, *tmp2 = NULL, *cur = head;

    while(cur && dummy){
        tmp1 = cur->next;
        tmp2 = dummy->next;

        cur->next = dummy;

        dummy->next = tmp1;

        cur = tmp1;
        dummy = tmp2;
    }
    }
};

7. 排序链表

Leetcode 148号问题。

归并排序链表版，相比数组，空间复杂度只需要O(1)。思想其实比较简单，关键是分的过程中，注意找到中间节点后断掉后半部分链表以及边界的处理问题。

class Solution {
     public ListNode sortList(ListNode head) {
        // 链表的归并排序
        if (head == null || head.next == null){
            return head;
        }
        ListNode mid = findMidNode(head);
        ListNode rightNode = mid.next;
        mid.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(rightNode);
        return merge(left,right);
    }

    // 找到链表中间节点
    public ListNode findMidNode(ListNode head){
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head.next;
        while (slow != null && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public ListNode merge(ListNode p, ListNode q){
        // 合并两个有序链表
        ListNode head = new ListNode(0), dummy = head;
        while (p != null && q != null){
            if (p.val < q.val){
                head.next = p;
                p = p.next;
            }else{
                head.next = q;
                q = q.next;
            }
            head = head.next;
        }
        head.next = p == null ? q:p;
        return dummy.next;

    }
}

8.分隔链表

很简单。。。。。

86. 分隔链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // 将小于x的节点放在x之前，原始相对位置不可以改变
        // 维护两个链表，一个是大于x的，一个是小于x的
       ListNode less = new ListNode(0);
       ListNode great = new ListNode(0);
       ListNode p = less ,q = great;
       while (head != null){
           ListNode next = head.next;
           if (head.val < x){
               p.next = head;
               p = p.next;
               p.next = null;
           }else{
               q.next = head;
               q = q.next;
               q.next = null;
           }
           head = next;
       }
        p.next = great.next;
        return less.next;
    }
}