last->link = newNode;
last = newNode;

r->link=p;
r = p;
p = p->link;

r->link=q;
r = q;
q = q->link;

#include<iostream>
using namespace std;
//#include"LinearList.h"
template <class T> ?//結點結構定義
struct LinkNode {
?? ?T data; ? ? ? ? ? ? ? ? ? ? ? ? //結點數(shù)據(jù)?
?? ?LinkNode<T>* link; ? ?//結點鏈接指針
?? ?LinkNode(LinkNode<T>* ptr = NULL) { link = ptr; } ?//構造函數(shù)?? ?
?? ?LinkNode(const T& item, LinkNode<T>* ptr = NULL) { data = item; link = ptr; }
};
template<class T>
class List{
protected:
?? ?struct LinkNode<T>* first;
public:
?? ?List() { first = new LinkNode<T>; } ? ? ? ? //構造函數(shù)
?? ?List(const T& x) { first = new LinkNode<T>(x); } ? ? ?//構造函數(shù)
?? ?List(List<T>& L); ? ? ? ? ? ? //復制構造函數(shù)
?? ?~List() { makeEmpty(); } ? ? ? ? ? ?//析構函數(shù)
?? ?void makeEmpty(); ? ? ? ? ? ? //將鏈表置空
?? ?int Length() const; ? ? ? ? ? ? //計算鏈表的長度
?? ?LinkNode<T>* getHead() const { return first; }
?? ?LinkNode<T>* Search(T x); ? ? ? ? ? //搜素數(shù)據(jù)為x的節(jié)點
?? ?LinkNode<T>* Locate(int i)const; ? ? ? ? ?//搜索第i個元素的地址
?? ?bool getData(int i, T& x) const; ? ? ? ? //取出第i個節(jié)點的數(shù)據(jù)
?? ?void setData(int i, T& x); ? ? ? ? ? //用x修改第i個元素的值
?? ?bool Insert(int i, T& x); ? ? ? ? ? //在第i個節(jié)點后插入新節(jié)點
?? ?bool Remove(int i, T& x); ? ? ? ? ? //刪除第i個節(jié)點數(shù)據(jù)返回到x中
?? ?bool IsEmpty() const ? ? ? ? ? ?//判斷表是否為NULL
?? ?{
?? ??? ?return first->link == NULL ? true : false;
?? ?}
?? ?bool IsFull() const { return false; } ? ? ? ?//判斷表滿
?? ?void InputFront(T ?endFlag); ? ? ? ? ?//倒序創(chuàng)建單鏈表
?? ?void InputRear(T endFlag); ? ? ? ? ? //正序創(chuàng)建單鏈表
?? ?void Output(); ? ? ? ? ? ? ?//輸出
};

#include"LinkList.h"
#include<iostream>
using namespace std;
template<class T>
List<T>::List(List<T>& L){
?? ?//復制構造函數(shù)
?? ?T value;
?? ?LinkNode<T>* srcptr = L.getHead();
?? ?LinkNode<T>* destptr = first = new LinkNode<T>;
?? ?while (srcptr->link != NULL) { ? ? ? ? ?//逐一賦值
?? ??? ?value = srcptr->link->data;
?? ??? ?destptr->link = new LinkNode<T>(value);
?? ??? ?destptr = destptr->link; ? ? ? ? ?//左值游動指針移動到下一個
?? ??? ?srcptr = srcptr->link; ? ? ? ? ? //右值游動指針移動到下一個
?? ?}
?? ?destptr->link = NULL;
}
template<class T>
void List<T>::makeEmpty() {
?? ?LinkNode<T> *q;
?? ?while(first->link!=NULL){
?? ??? ?q=first->link;
?? ??? ?first->link=q->link;
?? ??? ?delete q;
?? ?}
}
template<class T>
int List<T>::Length() const {
?? ?//計算帶附加頭節(jié)點的單鏈表的長度
?? ?LinkNode<T>* p = first->link;
?? ?int count = 0;
?? ?while (p != NULL) {
?? ??? ?count++;
?? ??? ?p = p->link;
?? ?}
?? ?return count;
}
template<class T>
LinkNode<T>* List<T>::Search(T x) {
?? ?//在表中搜索含數(shù)據(jù)x的節(jié)點，搜索成功時返回該節(jié)點的地址，否則返回NULL
?? ?LinkNode<T>* current = first->link;
?? ?while (current != NULL) {
?? ??? ?if (current->data == x) break;
?? ??? ?else current=current->link;
?? ?}
?? ?return current;
}
template<class T>
LinkNode<T>* List<T>::Locate(int i)const{
?? ?//定位函數(shù) 返回表中第i個節(jié)點的地址 如果i < 0 或者i 超過鏈表長度則返回NULL
?? ?if (i < 0) return NULL;
?? ?LinkNode<T>* current = first;
?? ?int m = 0;
?? ?while (current != NULL && m < i) {
?? ??? ?current = current->link;
?? ??? ?m++;
?? ?}
?? ?return current;
}
template<class T>
bool List<T>::getData(int i, T& x) const {
?? ?//取出鏈表中第i個節(jié)點的data
?? ?if (i <= 0) return NULL; ? ? ? ? ? ? //數(shù)據(jù)非法返回false
?? ?LinkNode<T>* current = Locate(i); ? ? ? ? //借助定位函數(shù)直接定位到相應的節(jié)點
?? ?if (current == NULL) return false; ? ? ? ? ? ? //i超過單鏈表的長度返回false
?? ?else {
?? ??? ?x = current->data;
?? ??? ?return true;
?? ?}
}
template<class T>
void List<T>::setData(int i, T& x) {
?? ?//設置鏈表的第i個元素為x
?? ?if (i <= 0) return;
?? ?LinkNode<T>* current = Locate(i);
?? ?if (current == NULL) return;
?? ?else current->data = x;
}
template<class T>
bool List<T>::Insert(int i, T& x) {
?? ?//在i個節(jié)點之后插入新節(jié)點
?? ?LinkNode<T>* current = Locate(i);
?? ?if (NULL == current) return false;
?? ?LinkNode<T>* newNode = new LinkNode<T>(x);
?? ?if (NULL == newNode)?
?? ??? ?cout << "存儲分配錯誤" << endl;
?? ?newNode->link = current->link;
?? ?current->link = newNode;
?? ?return true;
}
template<class T>
bool List<T>::Remove(int i, T& x) {
?? ?//將鏈表中第i個節(jié)點刪除 刪除成功返回true并將刪除的data存儲在x中
?? ?LinkNode<T>* current = Locate(i - 1); ? ? ? ?//定位到指向i節(jié)點的節(jié)點
?? ?if (NULL == current || NULL == current->link) return false; ? ? ? ? ? ? //不存在待刪除的節(jié)點
?? ?LinkNode<T>* del = current->link; ? ? ? ? //標記待刪除的節(jié)點
?? ?current->link = del->link; ? ? ? ? ? //重新拉鏈
?? ?x = del->data; ? ? ? ? ? ? ?//記錄下刪除節(jié)點的data
?? ?delete del; ? ? ? ? ? ? ? //釋放刪除節(jié)點
?? ?return true;
}
template<class T>
void List<T>::Output(){
?? ?//單鏈表的輸出函數(shù) ：將單鏈表中所有節(jié)點的data按邏輯順序輸出到屏幕上
?? ?LinkNode<T>* current = first->link; ? ? ? ?//創(chuàng)建遍歷指針
?? ?while (current != NULL) {
?? ??? ?cout<<current->data << ' ';
?? ??? ?current=current->link;
?? ?}
?? ?cout<<endl;
}
template<class T>
void List<T>::InputRear(T endFlag) {
?? ?//函數(shù)功能 ： 順序建立單鏈表
?? ?//函數(shù)參數(shù) ： 輸入結束標志的數(shù)據(jù)
?? ?LinkNode<T>* newNode, *last; ? ? ? ? ?//需要一個指針時刻標記結尾
?? ?T val;
?? ?makeEmpty();
?? ?cin >> val;
?? ?last = first; ? ? ? ? ? ? ?//首先令last指針指向頭節(jié)點
?? ?while (val != endFlag) {
?? ??? ?newNode = new LinkNode<T>(val);
?? ??? ?if (newNode== NULL)?
?? ??? ??? ?cout << "內(nèi)存分配錯誤" << endl;
?? ??? ?last->link = newNode;
?? ??? ?last = newNode;
?? ??? ?cin >> val;
?? ?}
?? ?last->link = NULL;
}
int main()
{
?? ?List<int> x;?
?? ?List<int> y;?
?? ?List<int> z;
?? ?LinkNode <int>*p,*q,*r;
?? ?cout<<"請輸入第一個鏈表(結束符為0)：";
?? ?x.InputRear(0);//以0作為結束符正序創(chuàng)建鏈表
?? ?cout<<"請輸入第二個鏈表(結束符為0)：";
?? ?y.InputRear(0);
?? ?p = x.getHead();
?? ?q = y.getHead();
?? ?r = z.getHead(); ? //新鏈表?
?? ?q = q->link;?
?? ?p = p->link;
?? ?cout << "歸并前的鏈表一：" << endl;
?? ?x.Output();
?? ?cout << "歸并前的鏈表二：" << endl;
?? ?y.Output();
?? ?while(p&&q)
?? ?{
?? ??? ?if(p->data <= q->data)
?? ??? ?{
?? ??? ??? ?r->link=p;
?? ??? ??? ?r = p;
?? ??? ??? ?p = p->link;
?? ??? ??? ?continue;
?? ??? ?}
?? ??? ?if(p->data>q->data)
?? ??? ?{
?? ??? ??? ?r->link=q;
?? ??? ??? ?r = q;
?? ??? ??? ?q = q->link;
?? ??? ??? ?continue;
?? ??? ?}
?? ?}
?? ?if(p) ? //歸并后對元素個數(shù)多的鏈表的單獨處理?
?? ?{
?? ??? ?while(p)
?? ??? ?{
?? ??? ??? ?r->link = p;
?? ??? ??? ?r = p;
?? ??? ??? ?p = p->link;
?? ??? ?}
?? ?}
?? ?if(q)
?? ?{
?? ??? ?while(q)
?? ??? ?{
?? ??? ??? ?r->link = q;
?? ??? ??? ?r = q;
?? ??? ??? ?q = q->link;
?? ??? ?}
?? ?}
?? ?cout<<"歸并后的鏈表為："<<endl;
?? ?z.Output();
}

/**
?* Definition for singly-linked list.
?* struct ListNode {
?* ? ? int val;
?* ? ? ListNode *next;
?* ? ? ListNode(int x) : val(x), next(NULL) {}
?* };
?*/
class Solution {
public:
? ? ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
? ? ? ? ListNode* p = new ListNode(0);
? ? ? ? ListNode* temp = p;
? ? ? ? while( l1 || l2 ){
? ? ? ? ? ? if(l1==NULL){
? ? ? ? ? ? ? ? p->next = l2;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else if(l2==NULL){
? ? ? ? ? ? ? ? p->next = l1;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if ( l1->val < l2->val ){
? ? ? ? ? ? ? ? ? ? p->next = l1;
? ? ? ? ? ? ? ? ? ? l1 = l1->next;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? p->next = l2;
? ? ? ? ? ? ? ? ? ? l2 = l2->next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? p=p->next;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return temp->next;
? ? }
};