链表交换、排序、相加

1、给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例: 给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		if (head == nullptr || head->next == nullptr)
			return head;
		ListNode* res = head->next;
		ListNode* pre = nullptr;
		ListNode* tmp = nullptr;
		while (head!=nullptr&&head->next != nullptr) {
			tmp = head->next;
			head->next = head->next->next;
			tmp->next = head;
			if (pre != nullptr) {
				pre->next = tmp;
				pre = head;
			}
			else
				pre = head;
			head = head->next;
		}
		if (head)
			pre->next = head;
		return res;
	}
};

2、首尾节点交错连接。

给定一个单链表 L，原节点顺序：L0→L1→…→Ln-1→Ln；编写一个算法，将节点顺序变更为：L0→Ln→L1→Ln-1→L2→Ln-2→…，即首尾节点交错链接。

题解：1，快慢指针找中点将原链表切分两段；2，将后面的链表元素存入栈中；3-遍历栈依次将栈顶元素插入到前面的链表合适的位置。

void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        //快慢指针找到链表中点并断开
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *right = slow->next;
        slow->next = nullptr;
        //将右边的链表压入栈中
        stack<ListNode *> s;
        while (right) {
            s.push(right);
            right = right->next;
        }
        ListNode *current = head;
        while (!s.empty()) {
            //取出栈顶元素
            ListNode *top = s.top();
            s.pop();
            ListNode *next = current->next;
            current->next = top;
            top->next = next;
            current = next;
        }
    }

如果题目要求不用额外的存储空间的话：先用快慢指针找到中间位置，将其分成两个链表，再将第二个链表反转，最后将反转的链表挨个插入第一个链表。

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head) return;
        ListNode* slow = head;
        ListNode* fast = head;

        while(slow && fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = reverseList(slow->next);
        ListNode* p = head;
        while(slow->next)
        {
            ListNode* tmp = slow->next;
            slow->next = tmp->next;

            tmp->next = p->next;
            p->next = tmp;
            p = tmp->next;
        }
    }

private:
    ListNode* reverseList(ListNode* head)
    {
        if (!head || !head->next) return head;
        ListNode* p = head;
        ListNode* newHead = head;

        while(p->next)
        {
            ListNode* tmp = p->next;
            p->next = tmp->next;
            tmp->next = newHead;
            newHead = tmp;
        }

        return newHead;
    }
};

3、单链表归并排序

题目：给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。在 O(n log n) 时间复杂度和常数级o(1)空间复杂度下，对链表进行排序.

输入：head = [4,2,1,3]
输出：[1,2,3,4]

具体做法如下。

首先求得链表的长度length，然后将链表拆分成子链表进行合并。
用 subLength 表示每次需要排序的子链表的长度，初始时subLength=1。
每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用合并两个有序链表的做法。
将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完毕。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode* prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr) {
                ListNode* head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* next = nullptr;
                if (curr != nullptr) {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};

4、两个链表生成相加链表
假设链表中每一个节点的值都在 0 – 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。链表中节点的值在0~9之间

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

输入：[9,3,7],[6,3] 返回值： {1,0,0,0}

/**
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
 
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if(head1 == NULL)
        {
            return head2;
        }
        if(head2 == NULL)
        {
            return head1;
        }
         
        stack<ListNode *> s1;
        stack<ListNode *> s2;
        while(head1 != NULL)
        {
            s1.push(head1);
            head1 = head1->next;
        }
        while(head2 != NULL)
        {
            s2.push(head2);
            head2 = head2->next;
        }
        int subsum = 0;
        while(!s1.empty()||!s2.empty())
        {
            int sum = subsum;
            if(!s1.empty())
            {
                sum += s1.top()->val;
                head1 = s1.top();
                s1.pop();
            }
            if(!s2.empty())
            {
                sum += s2.top()->val;
                if(s2.size()>s1.size())
                {
                    head1 = s2.top();
                }
                s2.pop();
            }
            if(sum < 10)
            {
                subsum = 0;
                head1->val = sum;
            }
            else
            {
                subsum = sum/10;
                head1->val = sum%10;
            }
        }
        if(subsum > 0)
        {
            head2 = new ListNode(subsum);
            head2->next = head1;
            return head2;
        }
         
        return head1;
    }
};

5、两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		while(l1==nullptr) return l2;
        while(l2==nullptr)return l1;
        ListNode* resHead=new ListNode;
        ListNode* resNext=resHead;
        int jinwei=0;
        int sum=0;
        while(l1!=nullptr&&l2!=nullptr){
            sum=jinwei+l1->val+l2->val;
            jinwei=sum/10;
            resNext->next=new ListNode(sum%10);
            resNext=resNext->next;
            l1=l1->next;
            l2=l2->next;
        }
        ListNode* last=(l1==nullptr?l2:l1);
        while(last!=nullptr){
            sum=jinwei+last->val;
            jinwei=sum/10;
            resNext->next=new ListNode(sum%10);
            resNext=resNext->next;
            last=last->next;
        }
        if (jinwei!=0) resNext->next=new ListNode(jinwei);
        return resHead->next;
	}
};

6、单向链表快速排序

首元素作为基准值key，使用两个Node指针slow和fast，slow初始时指向begin，fast初始时指向begin的下一个元素；
当fast没有到达链表末尾时，若fast指向的值大于等于key，更新fast指向fast的下一个元素；若小于key，则将更新slow指向slow的下一个元素，并将slow与fast指向的值交换，更新fast指向fast的下一个元素。
循环执行b直至fast到达链表尾部；交换链表头元素与slow指向元素值。
以slow为分割点将链表分为两部分，两个序列递归调用上述步骤排序完成。

struct Node {
	int value;
	Node* next;
	Node(int val) {
		value = val;
		next = nullptr;
	}
};
 
Node* partition(Node* begin, Node* end) {
	Node* slow = begin;
	Node* fast = begin->next;
	int val = begin->value;
	while (fast != end) {
		if (fast->value < val) {
			slow = slow->next;
			swap(slow->value, fast->value);
		}
		fast = fast->next;
	}
	swap(begin->value, slow->value);
	return slow;
}
 
void quicksort(Node* begin, Node* end) {
	if (begin != end) {
		Node* temp = partition(begin, end);
		quicksort(begin, temp);
		quicksort(temp->next, end);
	}
}

7、双向链表快速排序

ListNode * partion(ListNode * head, ListNode * slow, ListNode * fast)
{
    int tmp = 0;
    int pivot = 0;
    if ( !head )
    {
         printf("错误，头节点为空！/n");
         exit(1);
    }
    if ( !head->next )
    {
        return head->next;//就一个元素
    } 
    pivot = slow->data;
    while ( slow != fast )
    {
     //从后面往前换
        while ( slow != fast && fast->data >= pivot )
        {
            fast = fast->prev;
        }
    //交换high low
        tmp = slow->data;
        slow->data = fast->data;
        fast->data = tmp;
    //从前往后换
        while ( slow != fast && slow->data <= pivot )
        {
             slow = slow->next;
        }
    //交换high low
        tmp = slow->data;
        slow->data = fast->data;
        fast->data = tmp;
    }
    return slow;
}
//快排
void quick_sort(ListNode * head, ListNode * slow, ListNode * fast)
{
    ListNode * pivol = NULL;
    pivol = partion(head, slow, fast);
    if ( slow != pivol )
    {
         quick_sort(head, slow, pivol->prev);
    }
    if ( fast != pivol )
    {
        quick_sort(head, pivol->next, fast);
    }
}

原文链接：https://blog.csdn.net/u014618114/article/details/117949591

你可能也喜欢